{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Using Interval Variables and AddNoOverlap2D constraint for 2D rectangle packing\n",
    "\n",
    "Given a rectangular container and a set of rectangular items, the goal is to pack all items into the container respecting the orientation of items.\n",
    "All rectangles are orthogonal, i.e. they are parallel to the axes of the container.\n",
    "Thus, each item is defined by its length and width.\n",
    "\n",
    "This problem is also known as the 2D bin packing problem and is NP-hard.\n",
    "With CP-SAT, we can easily model this problem and solve smaller instances to optimality."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from ortools.sat.python import cp_model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Instance\n",
    "container = (40, 15)\n",
    "boxes = [\n",
    "    (11, 3),\n",
    "    (13, 3),\n",
    "    (9, 2),\n",
    "    (7, 2),\n",
    "    (9, 3),\n",
    "    (7, 3),\n",
    "    (11, 2),\n",
    "    (13, 2),\n",
    "    (11, 4),\n",
    "    (13, 4),\n",
    "    (3, 5),\n",
    "    (11, 2),\n",
    "    (2, 2),\n",
    "    (11, 3),\n",
    "    (2, 3),\n",
    "    (5, 4),\n",
    "    (6, 4),\n",
    "    (12, 2),\n",
    "    (1, 2),\n",
    "    (3, 5),\n",
    "    (13, 5),\n",
    "    (12, 4),\n",
    "    (1, 4),\n",
    "    (5, 2),\n",
    "    # (6,  2),  # add to make tight\n",
    "    # (6,3), # add to make infeasible\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pack(container, boxes, scale: int):\n",
    "    container = (container[0] * scale, container[1] * scale)\n",
    "    boxes = [(box[0] * scale, box[1] * scale) for box in boxes]\n",
    "    model = cp_model.CpModel()\n",
    "    # We have to create the variable for the bottom left corner of the boxes.\n",
    "    # We directly limit their range, such that the boxes are inside the container\n",
    "    x_vars = [\n",
    "        model.new_int_var(0, container[0] - box[0], name=f\"x1_{i}\")\n",
    "        for i, box in enumerate(boxes)\n",
    "    ]\n",
    "    y_vars = [\n",
    "        model.new_int_var(0, container[1] - box[1], name=f\"y1_{i}\")\n",
    "        for i, box in enumerate(boxes)\n",
    "    ]\n",
    "    # Interval variables are actually more like constraint containers, that are then passed to the no overlap constraint\n",
    "    # Note that we could also make size and end variables, but we don't need them here\n",
    "    x_interval_vars = [\n",
    "        model.new_interval_var(\n",
    "            start=x_vars[i], size=box[0], end=x_vars[i] + box[0], name=f\"x_interval_{i}\"\n",
    "        )\n",
    "        for i, box in enumerate(boxes)\n",
    "    ]\n",
    "    y_interval_vars = [\n",
    "        model.new_interval_var(\n",
    "            start=y_vars[i], size=box[1], end=y_vars[i] + box[1], name=f\"y_interval_{i}\"\n",
    "        )\n",
    "        for i, box in enumerate(boxes)\n",
    "    ]\n",
    "    # Enforce that no two rectangles overlap\n",
    "    model.add_no_overlap_2d(x_interval_vars, y_interval_vars)\n",
    "    # Solve!\n",
    "    solver = cp_model.CpSolver()\n",
    "    solver.parameters.log_search_progress = True\n",
    "    solver.log_callback = print\n",
    "    status = solver.solve(model)\n",
    "    assert status == cp_model.OPTIMAL"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n",
      "Starting CP-SAT solver v9.8.3296\n",
      "Starting CP-SAT solver v9.8.3296\n",
      "Parameters: log_search_progress: true\n",
      "Parameters: log_search_progress: true\n",
      "Setting number of workers to 16\n",
      "Setting number of workers to 16\n",
      "\n",
      "\n",
      "Initial satisfaction model '': (model_fingerprint: 0x932179154af0ad79)\n",
      "#Variables: 48\n",
      "  - 3 in [0,10]\n",
      "  - 6 in [0,11]\n",
      "  - 6 in [0,12]\n",
      "  - 9 in [0,13]\n",
      "  - 4 in [0,27]\n",
      "  - 2 in [0,28]\n",
      "  - 5 in [0,29]\n",
      "  - 2 in [0,31]\n",
      "  - 2 in [0,33]\n",
      "  - 1 in [0,34]\n",
      "  - 2 in [0,35]\n",
      "  - 2 in [0,37]\n",
      "  - 2 in [0,38]\n",
      "  - 2 in [0,39]\n",
      "#kInterval: 48\n",
      "#kLinear1: 48\n",
      "#kNoOverlap2D: 1 (#rectangles: 24)\n",
      "\n",
      "Initial satisfaction model '': (model_fingerprint: 0x932179154af0ad79)\n",
      "#Variables: 48\n",
      "  - 3 in [0,10]\n",
      "  - 6 in [0,11]\n",
      "  - 6 in [0,12]\n",
      "  - 9 in [0,13]\n",
      "  - 4 in [0,27]\n",
      "  - 2 in [0,28]\n",
      "  - 5 in [0,29]\n",
      "  - 2 in [0,31]\n",
      "  - 2 in [0,33]\n",
      "  - 1 in [0,34]\n",
      "  - 2 in [0,35]\n",
      "  - 2 in [0,37]\n",
      "  - 2 in [0,38]\n",
      "  - 2 in [0,39]\n",
      "#kInterval: 48\n",
      "#kLinear1: 48\n",
      "#kNoOverlap2D: 1 (#rectangles: 24)\n",
      "Starting presolve at 0.00s\n",
      "\n",
      "Starting presolve at 0.00s\n",
      "  1.38e-05s  0.00e+00d  [DetectDominanceRelations] \n",
      "  1.38e-05s  0.00e+00d  [DetectDominanceRelations] \n",
      "  1.04e-04s  0.00e+00d  [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1 \n",
      "  1.04e-04s  0.00e+00d  [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1 \n",
      "  2.16e-06s  0.00e+00d  [ExtractEncodingFromLinear] \n",
      "  2.16e-06s  0.00e+00d  [ExtractEncodingFromLinear] \n",
      "[Symmetry] Graph for symmetry has 193 nodes and 288 arcs.\n",
      "[Symmetry] Graph for symmetry has 193 nodes and 288 arcs.\n",
      "[Symmetry] Symmetry computation done. time: 7.5732e-05 dtime: 5.681e-05\n",
      "[Symmetry] #generators: 3, average support size: 4\n",
      "[Symmetry] Symmetry computation done. time: 7.5732e-05 dtime: 5.681e-05\n",
      "[Symmetry] 6 orbits with sizes: 2,2,2,2,2,2\n",
      "[Symmetry] #generators: 3, average support size: 4\n",
      "[Symmetry] 6 orbits with sizes: 2,2,2,2,2,2\n",
      "[Symmetry] Found orbitope of size 2 x 2\n",
      "[Symmetry] Found orbitope of size 2 x 2\n",
      "  1.15e-04s  5.00e-08d  [Probe] \n",
      "  1.15e-04s  5.00e-08d  [Probe] \n",
      "  2.96e-06s  0.00e+00d  [MaxClique] \n",
      "  2.96e-06s  0.00e+00d  [MaxClique] \n",
      "  1.42e-05s  0.00e+00d  [DetectDominanceRelations] \n",
      "  1.42e-05s  0.00e+00d  [DetectDominanceRelations] \n",
      "  8.39e-05s  0.00e+00d  [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1 \n",
      "  8.39e-05s  0.00e+00d  [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1 \n",
      "  6.88e-06s  0.00e+00d  [DetectDuplicateConstraints] \n",
      "  1.21e-06s  0.00e+00d  [DetectDifferentVariables] \n",
      "  6.88e-06s  0.00e+00d  [DetectDuplicateConstraints] \n",
      "  2.21e-06s  0.00e+00d  [DetectDominatedLinearConstraints] \n",
      "  1.21e-06s  0.00e+00d  [DetectDifferentVariables] \n",
      "  2.21e-06s  0.00e+00d  [DetectDominatedLinearConstraints] \n",
      "  2.56e-06s  0.00e+00d  [ProcessSetPPC] \n",
      "  2.56e-06s  0.00e+00d  [ProcessSetPPC] \n",
      "  1.98e-06s  0.00e+00d  [FindAlmostIdenticalLinearConstraints] \n",
      "  1.98e-06s  0.00e+00d  [FindAlmostIdenticalLinearConstraints] \n",
      "  1.62e-06s  0.00e+00d  [FindBigHorizontalLinearOverlap] \n",
      "  1.62e-06s  0.00e+00d  [FindBigHorizontalLinearOverlap] \n",
      "  2.19e-06s  2.40e-07d  [FindBigVerticalLinearOverlap] \n",
      "  2.19e-06s  2.40e-07d  [FindBigVerticalLinearOverlap] \n",
      "  2.01e-06s  0.00e+00d  [MergeClauses] \n",
      "  2.01e-06s  0.00e+00d  [MergeClauses] \n",
      "  8.27e-06s  0.00e+00d  [DetectDominanceRelations] \n",
      "  8.27e-06s  0.00e+00d  [DetectDominanceRelations] \n",
      "  7.17e-05s  0.00e+00d  [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1 \n",
      "  7.17e-05s  0.00e+00d  [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1 \n",
      "\n",
      "Presolve summary:\n",
      "  - 0 affine relations were detected.\n",
      "\n",
      "  - rule 'TODO dual: only one blocking constraint?' was applied 288 times.\n",
      "  - rule 'TODO symmetry: add symmetry breaking inequalities?' was applied 1 time.\n",
      "  - rule 'linear: always true' was applied 48 times.\n",
      "  - rule 'presolve: 0 unused variables removed.' was applied 1 time.\n",
      "  - rule 'presolve: iteration' was applied 1 time.\n",
      "Presolve summary:\n",
      "  - 0 affine relations were detected.\n",
      "  - rule 'TODO dual: only one blocking constraint?' was applied 288 times.\n",
      "  - rule 'TODO symmetry: add symmetry breaking inequalities?' was applied 1 time.\n",
      "  - rule 'linear: always true' was applied 48 times.\n",
      "  - rule 'presolve: 0 unused variables removed.' was applied 1 time.\n",
      "  - rule 'presolve: iteration' was applied 1 time.\n",
      "\n",
      "\n",
      "Presolved satisfaction model '': (model_fingerprint: 0x84a952283b593e1e)\n",
      "#Variables: 48\n",
      "  - 3 in [0,10]\n",
      "  - 6 in [0,11]\n",
      "  - 6 in [0,12]\n",
      "  - 9 in [0,13]\n",
      "  - 4 in [0,27]\n",
      "  - 2 in [0,28]\n",
      "  - 5 in [0,29]\n",
      "  - 2 in [0,31]\n",
      "  - 2 in [0,33]\n",
      "  - 1 in [0,34]\n",
      "  - 2 in [0,35]\n",
      "  - 2 in [0,37]\n",
      "  - 2 in [0,38]\n",
      "  - 2 in [0,39]\n",
      "#kInterval: 48\n",
      "#kNoOverlap2D: 1 (#rectangles: 24)\n",
      "Presolved satisfaction model '': (model_fingerprint: 0x84a952283b593e1e)\n",
      "#Variables: 48\n",
      "  - 3 in [0,10]\n",
      "  - 6 in [0,11]\n",
      "  - 6 in [0,12]\n",
      "  - 9 in [0,13]\n",
      "  - 4 in [0,27]\n",
      "  - 2 in [0,28]\n",
      "  - 5 in [0,29]\n",
      "  - 2 in [0,31]\n",
      "  - 2 in [0,33]\n",
      "  - 1 in [0,34]\n",
      "  - 2 in [0,35]\n",
      "  - 2 in [0,37]\n",
      "  - 2 in [0,38]\n",
      "  - 2 in [0,39]\n",
      "#kInterval: 48\n",
      "#kNoOverlap2D: 1 (#rectangles: 24)\n",
      "\n",
      "Preloading model.\n",
      "\n",
      "Preloading model.\n",
      "[Symmetry] Graph for symmetry has 193 nodes and 288 arcs.\n",
      "[Symmetry] Graph for symmetry has 193 nodes and 288 arcs.\n",
      "[Symmetry] Symmetry computation done. time: 5.5443e-05 dtime: 5.681e-05\n",
      "[Symmetry] #generators: 3, average support size: 4\n",
      "[Symmetry] Symmetry computation done. time: 5.5443e-05 dtime: 5.681e-05\n",
      "[Symmetry] Found orbitope of size 2 x 2\n",
      "[Symmetry] #generators: 3, average support size: 4\n",
      "[Symmetry] Found orbitope of size 2 x 2\n",
      "#Model   0.00s var:48/48 constraints:49/49\n",
      "#Model   0.00s var:48/48 constraints:49/49\n",
      "\n",
      "Starting search at 0.00s with 16 workers.\n",
      "\n",
      "7 full problem subsolvers: [default_lp, max_lp, no_lp, probing, probing_max_lp, quick_restart, quick_restart_no_lp]\n",
      "Starting search at 0.00s with 16 workers.\n",
      "7 full problem subsolvers: [default_lp, max_lp, no_lp, probing, probing_max_lp, quick_restart, quick_restart_no_lp]\n",
      "8 first solution subsolvers: [fj_long_default, fj_long_lin_default, fj_short_default, fj_short_lin_default, fs_random(2), fs_random_quick_restart(2)]\n",
      "8 first solution subsolvers: [fj_long_default, fj_long_lin_default, fj_short_default, fj_short_lin_default, fs_random(2), fs_random_quick_restart(2)]\n",
      "2 incomplete subsolvers: [feasibility_pump, rins/rens]\n",
      "2 helper subsolvers: [neighborhood_helper, synchronization_agent]\n",
      "2 incomplete subsolvers: [feasibility_pump, rins/rens]\n",
      "2 helper subsolvers: [neighborhood_helper, synchronization_agent]\n",
      "#1       0.03s probing (fixed_bools=0/108)\n",
      "#1       0.03s probing (fixed_bools=0/108)\n",
      "\n",
      "\n",
      "Task timing                          n [     min,      max]      avg      dev     time         n [     min,      max]      avg      dev    dtime\n",
      "               'default_lp':         1 [ 28.53ms,  28.53ms]  28.53ms   0.00ns  28.53ms         1 [  1.37ms,   1.37ms]   1.37ms   0.00ns   1.37ms\n",
      "         'feasibility_pump':         1 [138.51us, 138.51us] 138.51us   0.00ns 138.51us         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "          'fj_long_default':         1 [ 24.64ms,  24.64ms]  24.64ms   0.00ns  24.64ms         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "      'fj_long_lin_default':         1 [ 24.83ms,  24.83ms]  24.83ms   0.00ns  24.83ms         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "         'fj_short_default':         1 [ 27.82ms,  27.82ms]  27.82ms   0.00ns  27.82ms         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "     'fj_short_lin_default':         1 [ 24.79ms,  24.79ms]  24.79ms   0.00ns  24.79ms         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "                'fs_random':         1 [ 27.27ms,  27.27ms]  27.27ms   0.00ns  27.27ms         1 [  1.09ms,   1.09ms]   1.09ms   0.00ns   1.09ms\n",
      "                'fs_random':         1 [ 27.43ms,  27.43ms]  27.43ms   0.00ns  27.43ms         1 [  2.51ms,   2.51ms]   2.51ms   0.00ns   2.51ms\n",
      "  'fs_random_quick_restart':         1 [ 27.20ms,  27.20ms]  27.20ms   0.00ns  27.20ms         1 [  1.42ms,   1.42ms]   1.42ms   0.00ns   1.42ms\n",
      "  'fs_random_quick_restart':         1 [ 27.35ms,  27.35ms]  27.35ms   0.00ns  27.35ms         1 [  1.36ms,   1.36ms]   1.36ms   0.00ns   1.36ms\n",
      "                   'max_lp':         1 [ 28.37ms,  28.37ms]  28.37ms   0.00ns  28.37ms         1 [  1.64ms,   1.64ms]   1.64ms   0.00ns   1.64ms\n",
      "                    'no_lp':         1 [ 28.44ms,  28.44ms]  28.44ms   0.00ns  28.44ms         1 [  1.40ms,   1.40ms]   1.40ms   0.00ns   1.40ms\n",
      "                  'probing':         1 [ 28.15ms,  28.15ms]  28.15ms   0.00ns  28.15ms         1 [842.21us, 842.21us] 842.21us   0.00ns 842.21us\n",
      "           'probing_max_lp':         1 [ 28.07ms,  28.07ms]  28.07ms   0.00ns  28.07ms         1 [  1.84ms,   1.84ms]   1.84ms   0.00ns   1.84ms\n",
      "            'quick_restart':         1 [ 28.33ms,  28.33ms]  28.33ms   0.00ns  28.33ms         1 [  2.33ms,   2.33ms]   2.33ms   0.00ns   2.33ms\n",
      "      'quick_restart_no_lp':         1 [ 28.33ms,  28.33ms]  28.33ms   0.00ns  28.33ms         1 [  1.05ms,   1.05ms]   1.05ms   0.00ns   1.05ms\n",
      "                'rins/rens':         3 [640.07us,  19.65ms]   7.00ms   8.94ms  21.01ms         3 [ 40.00ns, 505.50us] 168.53us 238.28us 505.58us\n",
      "\n",
      "Task timing                          n [     min,      max]      avg      dev     time         n [     min,      max]      avg      dev    dtime\n",
      "               'default_lp':         1 [ 28.53ms,  28.53ms]  28.53ms   0.00ns  28.53ms         1 [  1.37ms,   1.37ms]   1.37ms   0.00ns   1.37ms\n",
      "         'feasibility_pump':         1 [138.51us, 138.51us] 138.51us   0.00ns 138.51us         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "          'fj_long_default':         1 [ 24.64ms,  24.64ms]  24.64ms   0.00ns  24.64ms         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "      'fj_long_lin_default':         1 [ 24.83ms,  24.83ms]  24.83ms   0.00ns  24.83ms         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "         'fj_short_default':         1 [ 27.82ms,  27.82ms]  27.82ms   0.00ns  27.82ms         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "     'fj_short_lin_default':         1 [ 24.79ms,  24.79ms]  24.79ms   0.00ns  24.79ms         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "                'fs_random':         1 [ 27.27ms,  27.27ms]  27.27ms   0.00ns  27.27ms         1 [  1.09ms,   1.09ms]   1.09ms   0.00ns   1.09ms\n",
      "                'fs_random':         1 [ 27.43ms,  27.43ms]  27.43ms   0.00ns  27.43ms         1 [  2.51ms,   2.51ms]   2.51ms   0.00ns   2.51ms\n",
      "  'fs_random_quick_restart':         1 [ 27.20ms,  27.20ms]  27.20ms   0.00ns  27.20ms         1 [  1.42ms,   1.42ms]   1.42ms   0.00ns   1.42ms\n",
      "  'fs_random_quick_restart':         1 [ 27.35ms,  27.35ms]  27.35ms   0.00ns  27.35ms         1 [  1.36ms,   1.36ms]   1.36ms   0.00ns   1.36ms\n",
      "                   'max_lp':         1 [ 28.37ms,  28.37ms]  28.37ms   0.00ns  28.37ms         1 [  1.64ms,   1.64ms]   1.64ms   0.00ns   1.64ms\n",
      "                    'no_lp':         1 [ 28.44ms,  28.44ms]  28.44ms   0.00ns  28.44ms         1 [  1.40ms,   1.40ms]   1.40ms   0.00ns   1.40ms\n",
      "                  'probing':         1 [ 28.15ms,  28.15ms]  28.15ms   0.00ns  28.15ms         1 [842.21us, 842.21us] 842.21us   0.00ns 842.21us\n",
      "           'probing_max_lp':         1 [ 28.07ms,  28.07ms]  28.07ms   0.00ns  28.07ms         1 [  1.84ms,   1.84ms]   1.84ms   0.00ns   1.84ms\n",
      "            'quick_restart':         1 [ 28.33ms,  28.33ms]  28.33ms   0.00ns  28.33ms         1 [  2.33ms,   2.33ms]   2.33ms   0.00ns   2.33ms\n",
      "      'quick_restart_no_lp':         1 [ 28.33ms,  28.33ms]  28.33ms   0.00ns  28.33ms         1 [  1.05ms,   1.05ms]   1.05ms   0.00ns   1.05ms\n",
      "                'rins/rens':         3 [640.07us,  19.65ms]   7.00ms   8.94ms  21.01ms         3 [ 40.00ns, 505.50us] 168.53us 238.28us 505.58us\n",
      "\n",
      "Search stats                  Bools  Conflicts  Branches  Restarts  BoolPropag  IntegerPropag\n",
      "               'default_lp':    300        301     1'704         6       7'167          5'127\n",
      "                'fs_random':    348        374     2'048         6       6'781          3'375\n",
      "                'fs_random':    468        755     2'806         4      17'977          5'442\n",
      "  'fs_random_quick_restart':    369        296     4'332        29       6'654          4'830\n",
      "  'fs_random_quick_restart':    372        291     3'982        29       8'148          4'379\n",
      "                   'max_lp':    212        305     1'084         3       4'844          2'202\n",
      "                    'no_lp':    303        304     1'789         6       7'353          5'239\n",
      "                  'probing':    108        280       578        11       2'463          4'124\n",
      "           'probing_max_lp':    108        100       184         6         612          1'236\n",
      "            'quick_restart':    334        433     4'058        43      13'904          4'778\n",
      "      'quick_restart_no_lp':    335        282     2'411        28       5'915          2'787\n",
      "\n",
      "Search stats                  Bools  Conflicts  Branches  Restarts  BoolPropag  IntegerPropag\n",
      "               'default_lp':    300        301     1'704         6       7'167          5'127\n",
      "                'fs_random':    348        374     2'048         6       6'781          3'375\n",
      "                'fs_random':    468        755     2'806         4      17'977          5'442\n",
      "  'fs_random_quick_restart':    369        296     4'332        29       6'654          4'830\n",
      "  'fs_random_quick_restart':    372        291     3'982        29       8'148          4'379\n",
      "                   'max_lp':    212        305     1'084         3       4'844          2'202\n",
      "                    'no_lp':    303        304     1'789         6       7'353          5'239\n",
      "                  'probing':    108        280       578        11       2'463          4'124\n",
      "           'probing_max_lp':    108        100       184         6         612          1'236\n",
      "            'quick_restart':    334        433     4'058        43      13'904          4'778\n",
      "      'quick_restart_no_lp':    335        282     2'411        28       5'915          2'787\n",
      "\n",
      "Lp stats             Component  Iterations  AddedCuts  OPTIMAL  DUAL_F.  DUAL_U.\n",
      "          'max_lp':          1         218         29      540        0        0\n",
      "  'probing_max_lp':          1         165         98      174        4        0\n",
      "\n",
      "Lp stats             Component  Iterations  AddedCuts  OPTIMAL  DUAL_F.  DUAL_U.\n",
      "          'max_lp':          1         218         29      540        0        0\n",
      "  'probing_max_lp':          1         165         98      174        4        0\n",
      "\n",
      "Lp dimension                                                      Final dimension of first component\n",
      "          'max_lp':    4 rows, 48 columns, 75 entries with magnitude in [7.627414e-01, 1.000000e+00]\n",
      "  'probing_max_lp':  20 rows, 48 columns, 330 entries with magnitude in [7.494389e-02, 1.000000e+00]\n",
      "\n",
      "Lp dimension                                                      Final dimension of first component\n",
      "          'max_lp':    4 rows, 48 columns, 75 entries with magnitude in [7.627414e-01, 1.000000e+00]\n",
      "  'probing_max_lp':  20 rows, 48 columns, 330 entries with magnitude in [7.494389e-02, 1.000000e+00]\n",
      "\n",
      "Lp debug             CutPropag  CutEqPropag  Adjust  Overflow  Bad  BadScaling\n",
      "          'max_lp':          0            0       0         0   40           0\n",
      "  'probing_max_lp':          0            0       0         0  113           0\n",
      "\n",
      "Lp debug             CutPropag  CutEqPropag  Adjust  Overflow  Bad  BadScaling\n",
      "          'max_lp':          0            0       0         0   40           0\n",
      "  'probing_max_lp':          0            0       0         0  113           0\n",
      "\n",
      "Lp pool              Constraints  Updates  Simplif  Merged  Shortened  Split  Strenghtened  Cuts/Call\n",
      "          'max_lp':           29        0        0       0          0      0             0      29/36\n",
      "  'probing_max_lp':           98        0        0       0          0      0            13     98/119\n",
      "\n",
      "Lp pool              Constraints  Updates  Simplif  Merged  Shortened  Split  Strenghtened  Cuts/Call\n",
      "          'max_lp':           29        0        0       0          0      0             0      29/36\n",
      "  'probing_max_lp':           98        0        0       0          0      0            13     98/119\n",
      "\n",
      "Lp Cut                         max_lp  probing_max_lp\n",
      "                        CG_K:       -               1\n",
      "                        CG_R:       5              19\n",
      "                    MIR_1_FF:       -               1\n",
      "                     MIR_1_R:      12              29\n",
      "  NoOverlap2dXCompletionTime:       5              21\n",
      "  NoOverlap2dYCompletionTime:       5              15\n",
      "                 ZERO_HALF_R:       2              12\n",
      "\n",
      "Lp Cut                         max_lp  probing_max_lp\n",
      "                        CG_K:       -               1\n",
      "                        CG_R:       5              19\n",
      "                    MIR_1_FF:       -               1\n",
      "                     MIR_1_R:      12              29\n",
      "  NoOverlap2dXCompletionTime:       5              21\n",
      "  NoOverlap2dYCompletionTime:       5              15\n",
      "                 ZERO_HALF_R:       2              12\n",
      "\n",
      "LNS stats       Improv/Calls  Closed  Difficulty  TimeLimit\n",
      "  'rins/rens':           3/3     67%        0.72       0.10\n",
      "\n",
      "LNS stats       Improv/Calls  Closed  Difficulty  TimeLimit\n",
      "  'rins/rens':           3/3     67%        0.72       0.10\n",
      "\n",
      "LS stats                   Batches  Restarts  LinMoves  GenMoves  CompoundMoves  WeightUpdates\n",
      "       'fj_long_default':        1         1         0       138             46              0\n",
      "   'fj_long_lin_default':        1         1         0       175              0             20\n",
      "      'fj_short_default':        1         1         0       282            166              0\n",
      "  'fj_short_lin_default':        1         1         0       231             63              0\n",
      "\n",
      "LS stats                   Batches  Restarts  LinMoves  GenMoves  CompoundMoves  WeightUpdates\n",
      "       'fj_long_default':        1         1         0       138             46              0\n",
      "   'fj_long_lin_default':        1         1         0       175              0             20\n",
      "      'fj_short_default':        1         1         0       282            166              0\n",
      "  'fj_short_lin_default':        1         1         0       231             63              0\n",
      "\n",
      "Solution repositories    Added  Queried  Ignored  Synchro\n",
      "  'feasible solutions':      1        0        0        1\n",
      "        'lp solutions':     11        3        0        3\n",
      "                'pump':      0        0\n",
      "\n",
      "Solution repositories    Added  Queried  Ignored  Synchro\n",
      "  'feasible solutions':      1        0        0        1\n",
      "        'lp solutions':     11        3        0        3\n",
      "                'pump':      0        0\n",
      "\n",
      "CpSolverResponse summary:\n",
      "status: OPTIMAL\n",
      "objective: NA\n",
      "best_bound: NA\n",
      "integers: 48\n",
      "booleans: 468\n",
      "conflicts: 755\n",
      "branches: 2806\n",
      "propagations: 17977\n",
      "integer_propagations: 5442\n",
      "restarts: 4\n",
      "lp_iterations: 0\n",
      "walltime: 0.0341316\n",
      "usertime: 0.0341317\n",
      "deterministic_time: 0.0173614\n",
      "gap_integral: 0\n",
      "solution_fingerprint: 0x397a0422cc046a6\n",
      "\n",
      "CpSolverResponse summary:\n",
      "status: OPTIMAL\n",
      "objective: NA\n",
      "best_bound: NA\n",
      "integers: 48\n",
      "booleans: 468\n",
      "conflicts: 755\n",
      "branches: 2806\n",
      "propagations: 17977\n",
      "integer_propagations: 5442\n",
      "restarts: 4\n",
      "lp_iterations: 0\n",
      "walltime: 0.0341316\n",
      "usertime: 0.0341317\n",
      "deterministic_time: 0.0173614\n",
      "gap_integral: 0\n",
      "solution_fingerprint: 0x397a0422cc046a6\n",
      "\n"
     ]
    }
   ],
   "source": [
    "pack(container, boxes, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n",
      "Starting CP-SAT solver v9.8.3296\n",
      "Starting CP-SAT solver v9.8.3296\n",
      "Parameters: log_search_progress: true\n",
      "Parameters: log_search_progress: true\n",
      "Setting number of workers to 16\n",
      "\n",
      "Setting number of workers to 16\n",
      "\n",
      "Initial satisfaction model '': (model_fingerprint: 0x26124a74348f784d)\n",
      "#Variables: 48\n",
      "  - 3 in [0,100]\n",
      "  - 6 in [0,110]\n",
      "  - 6 in [0,120]\n",
      "  - 9 in [0,130]\n",
      "  - 4 in [0,270]\n",
      "  - 2 in [0,280]\n",
      "  - 5 in [0,290]\n",
      "  - 2 in [0,310]\n",
      "  - 2 in [0,330]\n",
      "  - 1 in [0,340]\n",
      "  - 2 in [0,350]\n",
      "  - 2 in [0,370]\n",
      "  - 2 in [0,380]\n",
      "  - 2 in [0,390]\n",
      "#kInterval: 48\n",
      "#kLinear1: 48\n",
      "#kNoOverlap2D: 1 (#rectangles: 24)\n",
      "\n",
      "Initial satisfaction model '': (model_fingerprint: 0x26124a74348f784d)\n",
      "#Variables: 48\n",
      "  - 3 in [0,100]\n",
      "  - 6 in [0,110]\n",
      "  - 6 in [0,120]\n",
      "  - 9 in [0,130]\n",
      "  - 4 in [0,270]\n",
      "  - 2 in [0,280]\n",
      "  - 5 in [0,290]\n",
      "  - 2 in [0,310]\n",
      "  - 2 in [0,330]\n",
      "  - 1 in [0,340]\n",
      "  - 2 in [0,350]\n",
      "  - 2 in [0,370]\n",
      "  - 2 in [0,380]\n",
      "  - 2 in [0,390]\n",
      "#kInterval: 48\n",
      "#kLinear1: 48\n",
      "#kNoOverlap2D: 1 (#rectangles: 24)\n",
      "\n",
      "Starting presolve at 0.00s\n",
      "Starting presolve at 0.00s\n",
      "  1.43e-05s  0.00e+00d  [DetectDominanceRelations] \n",
      "  1.43e-05s  0.00e+00d  [DetectDominanceRelations] \n",
      "  9.59e-05s  0.00e+00d  [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1 \n",
      "  9.59e-05s  0.00e+00d  [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1 \n",
      "  1.78e-06s  0.00e+00d  [ExtractEncodingFromLinear] \n",
      "  1.78e-06s  0.00e+00d  [ExtractEncodingFromLinear] \n",
      "[Symmetry] Graph for symmetry has 193 nodes and 288 arcs.\n",
      "[Symmetry] Graph for symmetry has 193 nodes and 288 arcs.\n",
      "[Symmetry] Symmetry computation done. time: 5.6476e-05 dtime: 5.681e-05\n",
      "[Symmetry] Symmetry computation done. time: 5.6476e-05 dtime: 5.681e-05\n",
      "[Symmetry] #generators: 3, average support size: 4\n",
      "[Symmetry] #generators: 3, average support size: 4\n",
      "[Symmetry] 6 orbits with sizes: 2,2,2,2,2,2\n",
      "[Symmetry] 6 orbits with sizes: 2,2,2,2,2,2\n",
      "[Symmetry] Found orbitope of size 2 x 2\n",
      "[Symmetry] Found orbitope of size 2 x 2\n",
      "  1.02e-04s  5.00e-08d  [Probe] \n",
      "  1.02e-04s  5.00e-08d  [Probe] \n",
      "  3.08e-06s  0.00e+00d  [MaxClique] \n",
      "  3.08e-06s  0.00e+00d  [MaxClique] \n",
      "  1.52e-05s  0.00e+00d  [DetectDominanceRelations] \n",
      "  1.52e-05s  0.00e+00d  [DetectDominanceRelations] \n",
      "  8.26e-05s  0.00e+00d  [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1 \n",
      "  8.26e-05s  0.00e+00d  [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1 \n",
      "  9.33e-06s  0.00e+00d  [DetectDuplicateConstraints] \n",
      "  7.71e-07s  0.00e+00d  [DetectDifferentVariables] \n",
      "  1.15e-06s  0.00e+00d  [DetectDominatedLinearConstraints] \n",
      "  9.33e-06s  0.00e+00d  [DetectDuplicateConstraints] \n",
      "  1.52e-06s  0.00e+00d  [ProcessSetPPC] \n",
      "  1.66e-06s  0.00e+00d  [FindAlmostIdenticalLinearConstraints] \n",
      "  7.71e-07s  0.00e+00d  [DetectDifferentVariables] \n",
      "  1.15e-06s  0.00e+00d  [DetectDominatedLinearConstraints] \n",
      "  1.52e-06s  0.00e+00d  [ProcessSetPPC] \n",
      "  1.66e-06s  0.00e+00d  [FindAlmostIdenticalLinearConstraints] \n",
      "  1.23e-06s  0.00e+00d  [FindBigHorizontalLinearOverlap] \n",
      "  1.23e-06s  0.00e+00d  [FindBigHorizontalLinearOverlap] \n",
      "  1.59e-06s  2.40e-07d  [FindBigVerticalLinearOverlap] \n",
      "  1.59e-06s  2.40e-07d  [FindBigVerticalLinearOverlap] \n",
      "  1.56e-06s  0.00e+00d  [MergeClauses] \n",
      "  1.56e-06s  0.00e+00d  [MergeClauses] \n",
      "  9.57e-06s  0.00e+00d  [DetectDominanceRelations] \n",
      "  9.57e-06s  0.00e+00d  [DetectDominanceRelations] \n",
      "  6.20e-05s  0.00e+00d  [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1 \n",
      "  6.20e-05s  0.00e+00d  [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1 \n",
      "\n",
      "\n",
      "Presolve summary:\n",
      "  - 0 affine relations were detected.\n",
      "Presolve summary:\n",
      "  - rule 'TODO dual: only one blocking constraint?' was applied 288 times.\n",
      "  - rule 'TODO symmetry: add symmetry breaking inequalities?' was applied 1 time.\n",
      "  - 0 affine relations were detected.\n",
      "  - rule 'TODO dual: only one blocking constraint?' was applied 288 times.\n",
      "  - rule 'TODO symmetry: add symmetry breaking inequalities?' was applied 1 time.\n",
      "  - rule 'linear: always true' was applied 48 times.\n",
      "  - rule 'linear: always true' was applied 48 times.\n",
      "  - rule 'presolve: 0 unused variables removed.' was applied 1 time.\n",
      "  - rule 'presolve: 0 unused variables removed.' was applied 1 time.\n",
      "  - rule 'presolve: iteration' was applied 1 time.\n",
      "  - rule 'presolve: iteration' was applied 1 time.\n",
      "\n",
      "\n",
      "Presolved satisfaction model '': (model_fingerprint: 0x23daaa54bf3ffcd3)\n",
      "#Variables: 48\n",
      "  - 3 in [0,100]\n",
      "  - 6 in [0,110]\n",
      "  - 6 in [0,120]\n",
      "  - 9 in [0,130]\n",
      "  - 4 in [0,270]\n",
      "  - 2 in [0,280]\n",
      "  - 5 in [0,290]\n",
      "  - 2 in [0,310]\n",
      "  - 2 in [0,330]\n",
      "  - 1 in [0,340]\n",
      "  - 2 in [0,350]\n",
      "  - 2 in [0,370]\n",
      "  - 2 in [0,380]\n",
      "  - 2 in [0,390]\n",
      "#kInterval: 48\n",
      "#kNoOverlap2D: 1 (#rectangles: 24)\n",
      "Presolved satisfaction model '': (model_fingerprint: 0x23daaa54bf3ffcd3)\n",
      "#Variables: 48\n",
      "  - 3 in [0,100]\n",
      "  - 6 in [0,110]\n",
      "  - 6 in [0,120]\n",
      "  - 9 in [0,130]\n",
      "  - 4 in [0,270]\n",
      "  - 2 in [0,280]\n",
      "  - 5 in [0,290]\n",
      "  - 2 in [0,310]\n",
      "  - 2 in [0,330]\n",
      "  - 1 in [0,340]\n",
      "  - 2 in [0,350]\n",
      "  - 2 in [0,370]\n",
      "  - 2 in [0,380]\n",
      "  - 2 in [0,390]\n",
      "#kInterval: 48\n",
      "#kNoOverlap2D: 1 (#rectangles: 24)\n",
      "\n",
      "\n",
      "Preloading model.\n",
      "Preloading model.\n",
      "[Symmetry] Graph for symmetry has 193 nodes and 288 arcs.\n",
      "[Symmetry] Graph for symmetry has 193 nodes and 288 arcs.\n",
      "[Symmetry] Symmetry computation done. time: 5.0635e-05 dtime: 5.681e-05\n",
      "[Symmetry] Symmetry computation done. time: 5.0635e-05 dtime: 5.681e-05\n",
      "[Symmetry] #generators: 3, average support size: 4\n",
      "[Symmetry] #generators: 3, average support size: 4\n",
      "[Symmetry] Found orbitope of size 2 x 2\n",
      "[Symmetry] Found orbitope of size 2 x 2\n",
      "#Model   0.00s var:48/48 constraints:49/49\n",
      "#Model   0.00s var:48/48 constraints:49/49\n",
      "\n",
      "\n",
      "Starting search at 0.00s with 16 workers.\n",
      "Starting search at 0.00s with 16 workers.\n",
      "7 full problem subsolvers: [default_lp, max_lp, no_lp, probing, probing_max_lp, quick_restart, quick_restart_no_lp]\n",
      "7 full problem subsolvers: [default_lp, max_lp, no_lp, probing, probing_max_lp, quick_restart, quick_restart_no_lp]\n",
      "8 first solution subsolvers: [fj_long_default, fj_long_lin_default, fj_short_default, fj_short_lin_default, fs_random(2), fs_random_quick_restart(2)]\n",
      "2 incomplete subsolvers: [feasibility_pump, rins/rens]\n",
      "2 helper subsolvers: [neighborhood_helper, synchronization_agent]\n",
      "8 first solution subsolvers: [fj_long_default, fj_long_lin_default, fj_short_default, fj_short_lin_default, fs_random(2), fs_random_quick_restart(2)]\n",
      "2 incomplete subsolvers: [feasibility_pump, rins/rens]\n",
      "2 helper subsolvers: [neighborhood_helper, synchronization_agent]\n",
      "#1       0.01s probing_max_lp (fixed_bools=0/101)\n",
      "#1       0.01s probing_max_lp (fixed_bools=0/101)\n",
      "\n",
      "\n",
      "Task timing                          n [     min,      max]      avg      dev     time         n [     min,      max]      avg      dev    dtime\n",
      "               'default_lp':         1 [ 11.34ms,  11.34ms]  11.34ms   0.00ns  11.34ms         1 [  5.30ms,   5.30ms]   5.30ms   0.00ns   5.30ms\n",
      "         'feasibility_pump':         1 [136.49us, 136.49us] 136.49us   0.00ns 136.49us         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "          'fj_long_default':         1 [  1.42ms,   1.42ms]   1.42ms   0.00ns   1.42ms         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "      'fj_long_lin_default':         1 [  1.20ms,   1.20ms]   1.20ms   0.00ns   1.20ms         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "         'fj_short_default':         1 [  1.63ms,   1.63ms]   1.63ms   0.00ns   1.63ms         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "     'fj_short_lin_default':         1 [  2.05ms,   2.05ms]   2.05ms   0.00ns   2.05ms         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "                'fs_random':         1 [  6.20ms,   6.20ms]   6.20ms   0.00ns   6.20ms         1 [232.89us, 232.89us] 232.89us   0.00ns 232.89us\n",
      "                'fs_random':         1 [915.62us, 915.62us] 915.62us   0.00ns 915.62us         1 [ 19.46us,  19.46us]  19.46us   0.00ns  19.46us\n",
      "  'fs_random_quick_restart':         1 [  6.18ms,   6.18ms]   6.18ms   0.00ns   6.18ms         1 [476.06us, 476.06us] 476.06us   0.00ns 476.06us\n",
      "  'fs_random_quick_restart':         1 [900.90us, 900.90us] 900.90us   0.00ns 900.90us         1 [ 30.27us,  30.27us]  30.27us   0.00ns  30.27us\n",
      "                   'max_lp':         1 [ 11.27ms,  11.27ms]  11.27ms   0.00ns  11.27ms         1 [541.97us, 541.97us] 541.97us   0.00ns 541.97us\n",
      "                    'no_lp':         1 [ 11.30ms,  11.30ms]  11.30ms   0.00ns  11.30ms         1 [  5.30ms,   5.30ms]   5.30ms   0.00ns   5.30ms\n",
      "                  'probing':         1 [ 11.22ms,  11.22ms]  11.22ms   0.00ns  11.22ms         1 [306.68us, 306.68us] 306.68us   0.00ns 306.68us\n",
      "           'probing_max_lp':         1 [ 11.20ms,  11.20ms]  11.20ms   0.00ns  11.20ms         1 [731.61us, 731.61us] 731.61us   0.00ns 731.61us\n",
      "            'quick_restart':         1 [ 11.32ms,  11.32ms]  11.32ms   0.00ns  11.32ms         1 [  1.50ms,   1.50ms]   1.50ms   0.00ns   1.50ms\n",
      "      'quick_restart_no_lp':         1 [ 11.22ms,  11.22ms]  11.22ms   0.00ns  11.22ms         1 [  1.44ms,   1.44ms]   1.44ms   0.00ns   1.44ms\n",
      "                'rins/rens':         1 [740.19us, 740.19us] 740.19us   0.00ns 740.19us         1 [ 40.00ns,  40.00ns]  40.00ns   0.00ns  40.00ns\n",
      "\n",
      "Task timing                          n [     min,      max]      avg      dev     time         n [     min,      max]      avg      dev    dtime\n",
      "               'default_lp':         1 [ 11.34ms,  11.34ms]  11.34ms   0.00ns  11.34ms         1 [  5.30ms,   5.30ms]   5.30ms   0.00ns   5.30ms\n",
      "         'feasibility_pump':         1 [136.49us, 136.49us] 136.49us   0.00ns 136.49us         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "          'fj_long_default':         1 [  1.42ms,   1.42ms]   1.42ms   0.00ns   1.42ms         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "      'fj_long_lin_default':         1 [  1.20ms,   1.20ms]   1.20ms   0.00ns   1.20ms         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "         'fj_short_default':         1 [  1.63ms,   1.63ms]   1.63ms   0.00ns   1.63ms         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "     'fj_short_lin_default':         1 [  2.05ms,   2.05ms]   2.05ms   0.00ns   2.05ms         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "                'fs_random':         1 [  6.20ms,   6.20ms]   6.20ms   0.00ns   6.20ms         1 [232.89us, 232.89us] 232.89us   0.00ns 232.89us\n",
      "                'fs_random':         1 [915.62us, 915.62us] 915.62us   0.00ns 915.62us         1 [ 19.46us,  19.46us]  19.46us   0.00ns  19.46us\n",
      "  'fs_random_quick_restart':         1 [  6.18ms,   6.18ms]   6.18ms   0.00ns   6.18ms         1 [476.06us, 476.06us] 476.06us   0.00ns 476.06us\n",
      "  'fs_random_quick_restart':         1 [900.90us, 900.90us] 900.90us   0.00ns 900.90us         1 [ 30.27us,  30.27us]  30.27us   0.00ns  30.27us\n",
      "                   'max_lp':         1 [ 11.27ms,  11.27ms]  11.27ms   0.00ns  11.27ms         1 [541.97us, 541.97us] 541.97us   0.00ns 541.97us\n",
      "                    'no_lp':         1 [ 11.30ms,  11.30ms]  11.30ms   0.00ns  11.30ms         1 [  5.30ms,   5.30ms]   5.30ms   0.00ns   5.30ms\n",
      "                  'probing':         1 [ 11.22ms,  11.22ms]  11.22ms   0.00ns  11.22ms         1 [306.68us, 306.68us] 306.68us   0.00ns 306.68us\n",
      "           'probing_max_lp':         1 [ 11.20ms,  11.20ms]  11.20ms   0.00ns  11.20ms         1 [731.61us, 731.61us] 731.61us   0.00ns 731.61us\n",
      "            'quick_restart':         1 [ 11.32ms,  11.32ms]  11.32ms   0.00ns  11.32ms         1 [  1.50ms,   1.50ms]   1.50ms   0.00ns   1.50ms\n",
      "      'quick_restart_no_lp':         1 [ 11.22ms,  11.22ms]  11.22ms   0.00ns  11.22ms         1 [  1.44ms,   1.44ms]   1.44ms   0.00ns   1.44ms\n",
      "                'rins/rens':         1 [740.19us, 740.19us] 740.19us   0.00ns 740.19us         1 [ 40.00ns,  40.00ns]  40.00ns   0.00ns  40.00ns\n",
      "\n",
      "Search stats                  Bools  Conflicts  Branches  Restarts  BoolPropag  IntegerPropag\n",
      "               'default_lp':    523        513     1'202         5      24'038         23'949\n",
      "                'fs_random':    359        340       700         4         889          1'043\n",
      "                'fs_random':     69         58        72         1         110            130\n",
      "  'fs_random_quick_restart':    274        204     1'098        20       2'919          1'307\n",
      "  'fs_random_quick_restart':     62         44       107         4         141            152\n",
      "                   'max_lp':    281        262       321         2         690            680\n",
      "                    'no_lp':    523        513     1'202         5      24'038         23'949\n",
      "                  'probing':    152        142       300         6         718          1'954\n",
      "           'probing_max_lp':    101         62       107         5         122            887\n",
      "            'quick_restart':    502        350     2'599        35       9'518          3'280\n",
      "      'quick_restart_no_lp':    476        370     2'850        37       9'079          3'357\n",
      "\n",
      "Search stats                  Bools  Conflicts  Branches  Restarts  BoolPropag  IntegerPropag\n",
      "               'default_lp':    523        513     1'202         5      24'038         23'949\n",
      "                'fs_random':    359        340       700         4         889          1'043\n",
      "                'fs_random':     69         58        72         1         110            130\n",
      "  'fs_random_quick_restart':    274        204     1'098        20       2'919          1'307\n",
      "  'fs_random_quick_restart':     62         44       107         4         141            152\n",
      "                   'max_lp':    281        262       321         2         690            680\n",
      "                    'no_lp':    523        513     1'202         5      24'038         23'949\n",
      "                  'probing':    152        142       300         6         718          1'954\n",
      "           'probing_max_lp':    101         62       107         5         122            887\n",
      "            'quick_restart':    502        350     2'599        35       9'518          3'280\n",
      "      'quick_restart_no_lp':    476        370     2'850        37       9'079          3'357\n",
      "\n",
      "Lp stats             Component  Iterations  AddedCuts  OPTIMAL  DUAL_F.  DUAL_U.\n",
      "          'max_lp':          1          60         26      282        0        0\n",
      "  'probing_max_lp':          1          97         58      129        1        0\n",
      "\n",
      "Lp stats             Component  Iterations  AddedCuts  OPTIMAL  DUAL_F.  DUAL_U.\n",
      "          'max_lp':          1          60         26      282        0        0\n",
      "  'probing_max_lp':          1          97         58      129        1        0\n",
      "\n",
      "Lp dimension                                                      Final dimension of first component\n",
      "          'max_lp':    4 rows, 48 columns, 77 entries with magnitude in [1.000000e+00, 1.000000e+00]\n",
      "  'probing_max_lp':  21 rows, 48 columns, 330 entries with magnitude in [2.648861e-01, 1.000000e+00]\n",
      "\n",
      "Lp dimension                                                      Final dimension of first component\n",
      "          'max_lp':    4 rows, 48 columns, 77 entries with magnitude in [1.000000e+00, 1.000000e+00]\n",
      "  'probing_max_lp':  21 rows, 48 columns, 330 entries with magnitude in [2.648861e-01, 1.000000e+00]\n",
      "\n",
      "Lp debug             CutPropag  CutEqPropag  Adjust  Overflow  Bad  BadScaling\n",
      "          'max_lp':          0            0       0         0   36           0\n",
      "  'probing_max_lp':          0            0       0         0  209           0\n",
      "\n",
      "Lp debug             CutPropag  CutEqPropag  Adjust  Overflow  Bad  BadScaling\n",
      "          'max_lp':          0            0       0         0   36           0\n",
      "  'probing_max_lp':          0            0       0         0  209           0\n",
      "\n",
      "Lp pool              Constraints  Updates  Simplif  Merged  Shortened  Split  Strenghtened  Cuts/Call\n",
      "          'max_lp':           26        0        0       0          0      0             0      26/29\n",
      "  'probing_max_lp':           58        0        0       0          0      0             0      58/69\n",
      "\n",
      "Lp pool              Constraints  Updates  Simplif  Merged  Shortened  Split  Strenghtened  Cuts/Call\n",
      "          'max_lp':           26        0        0       0          0      0             0      26/29\n",
      "  'probing_max_lp':           58        0        0       0          0      0             0      58/69\n",
      "\n",
      "Lp Cut                               max_lp  probing_max_lp\n",
      "                             CG_FF:       -               1\n",
      "                              CG_R:       5               8\n",
      "                           MIR_1_R:      10              26\n",
      "        NoOverlap2dXCompletionTime:       5               9\n",
      "        NoOverlap2dYCompletionTime:       5              11\n",
      "  NoOverlap2dYCompletionTimeMirror:       -               1\n",
      "                       ZERO_HALF_R:       1               2\n",
      "\n",
      "Lp Cut                               max_lp  probing_max_lp\n",
      "                             CG_FF:       -               1\n",
      "                              CG_R:       5               8\n",
      "                           MIR_1_R:      10              26\n",
      "        NoOverlap2dXCompletionTime:       5               9\n",
      "        NoOverlap2dYCompletionTime:       5              11\n",
      "  NoOverlap2dYCompletionTimeMirror:       -               1\n",
      "                       ZERO_HALF_R:       1               2\n",
      "\n",
      "LNS stats       Improv/Calls  Closed  Difficulty  TimeLimit\n",
      "  'rins/rens':           1/1    100%        0.71       0.10\n",
      "\n",
      "LNS stats       Improv/Calls  Closed  Difficulty  TimeLimit\n",
      "  'rins/rens':           1/1    100%        0.71       0.10\n",
      "\n",
      "LS stats                   Batches  Restarts  LinMoves  GenMoves  CompoundMoves  WeightUpdates\n",
      "       'fj_long_default':        1         1         0        31             31              0\n",
      "   'fj_long_lin_default':        1         1         0        27              0              0\n",
      "      'fj_short_default':        1         1         0        27             27              0\n",
      "  'fj_short_lin_default':        1         1         0        30             30              0\n",
      "\n",
      "LS stats                   Batches  Restarts  LinMoves  GenMoves  CompoundMoves  WeightUpdates\n",
      "       'fj_long_default':        1         1         0        31             31              0\n",
      "   'fj_long_lin_default':        1         1         0        27              0              0\n",
      "      'fj_short_default':        1         1         0        27             27              0\n",
      "  'fj_short_lin_default':        1         1         0        30             30              0\n",
      "\n",
      "Solution repositories    Added  Queried  Ignored  Synchro\n",
      "  'feasible solutions':      1        0        0        1\n",
      "        'lp solutions':      4        1        0        2\n",
      "                'pump':      0        0\n",
      "Solution repositories    Added  Queried  Ignored  Synchro\n",
      "  'feasible solutions':      1        0        0        1\n",
      "        'lp solutions':      4        1        0        2\n",
      "                'pump':      0        0\n",
      "\n",
      "\n",
      "CpSolverResponse summary:\n",
      "status: OPTIMAL\n",
      "objective: NA\n",
      "best_bound: NA\n",
      "integers: 48\n",
      "booleans: 359\n",
      "conflicts: 340\n",
      "branches: 700\n",
      "propagations: 889\n",
      "integer_propagations: 1043\n",
      "restarts: 4\n",
      "lp_iterations: 0\n",
      "walltime: 0.0177736\n",
      "usertime: 0.0177736\n",
      "deterministic_time: 0.0158837\n",
      "gap_integral: 0\n",
      "solution_fingerprint: 0xd22bad8897e41992\n",
      "\n",
      "CpSolverResponse summary:\n",
      "status: OPTIMAL\n",
      "objective: NA\n",
      "best_bound: NA\n",
      "integers: 48\n",
      "booleans: 359\n",
      "conflicts: 340\n",
      "branches: 700\n",
      "propagations: 889\n",
      "integer_propagations: 1043\n",
      "restarts: 4\n",
      "lp_iterations: 0\n",
      "walltime: 0.0177736\n",
      "usertime: 0.0177736\n",
      "deterministic_time: 0.0158837\n",
      "gap_integral: 0\n",
      "solution_fingerprint: 0xd22bad8897e41992\n",
      "\n"
     ]
    }
   ],
   "source": [
    "pack(container, boxes, 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n",
      "Starting CP-SAT solver v9.8.3296\n",
      "Parameters: log_search_progress: true\n",
      "Starting CP-SAT solver v9.8.3296\n",
      "Parameters: log_search_progress: true\n",
      "Setting number of workers to 16\n",
      "Setting number of workers to 16\n",
      "\n",
      "\n",
      "Initial satisfaction model '': (model_fingerprint: 0x74eb0f3c80f0c54e)\n",
      "#Variables: 48\n",
      "  - 3 in [0,1000]\n",
      "  - 6 in [0,1100]\n",
      "  - 6 in [0,1200]\n",
      "  - 9 in [0,1300]\n",
      "  - 4 in [0,2700]\n",
      "  - 2 in [0,2800]\n",
      "  - 5 in [0,2900]\n",
      "  - 2 in [0,3100]\n",
      "  - 2 in [0,3300]\n",
      "  - 1 in [0,3400]\n",
      "  - 2 in [0,3500]\n",
      "  - 2 in [0,3700]\n",
      "  - 2 in [0,3800]\n",
      "  - 2 in [0,3900]\n",
      "#kInterval: 48\n",
      "#kLinear1: 48\n",
      "#kNoOverlap2D: 1 (#rectangles: 24)\n",
      "\n",
      "Initial satisfaction model '': (model_fingerprint: 0x74eb0f3c80f0c54e)\n",
      "#Variables: 48\n",
      "  - 3 in [0,1000]\n",
      "  - 6 in [0,1100]\n",
      "  - 6 in [0,1200]\n",
      "  - 9 in [0,1300]\n",
      "  - 4 in [0,2700]\n",
      "  - 2 in [0,2800]\n",
      "  - 5 in [0,2900]\n",
      "  - 2 in [0,3100]\n",
      "  - 2 in [0,3300]\n",
      "  - 1 in [0,3400]\n",
      "  - 2 in [0,3500]\n",
      "  - 2 in [0,3700]\n",
      "  - 2 in [0,3800]\n",
      "  - 2 in [0,3900]\n",
      "#kInterval: 48\n",
      "#kLinear1: 48\n",
      "#kNoOverlap2D: 1 (#rectangles: 24)\n",
      "Starting presolve at 0.00s\n",
      "\n",
      "Starting presolve at 0.00s\n",
      "  1.49e-05s  0.00e+00d  [DetectDominanceRelations] \n",
      "  1.49e-05s  0.00e+00d  [DetectDominanceRelations] \n",
      "  9.59e-05s  0.00e+00d  [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1 \n",
      "  9.59e-05s  0.00e+00d  [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1 \n",
      "  2.06e-06s  0.00e+00d  [ExtractEncodingFromLinear] \n",
      "  2.06e-06s  0.00e+00d  [ExtractEncodingFromLinear] \n",
      "[Symmetry] Graph for symmetry has 193 nodes and 288 arcs.\n",
      "[Symmetry] Graph for symmetry has 193 nodes and 288 arcs.\n",
      "[Symmetry] Symmetry computation done. time: 5.5734e-05 dtime: 5.681e-05\n",
      "[Symmetry] #generators: 3, average support size: 4\n",
      "[Symmetry] Symmetry computation done. time: 5.5734e-05 dtime: 5.681e-05\n",
      "[Symmetry] 6 orbits with sizes: 2,2,2,2,2,2\n",
      "[Symmetry] Found orbitope of size 2 x 2\n",
      "[Symmetry] #generators: 3, average support size: 4\n",
      "[Symmetry] 6 orbits with sizes: 2,2,2,2,2,2\n",
      "[Symmetry] Found orbitope of size 2 x 2\n",
      "  1.04e-04s  5.00e-08d  [Probe] \n",
      "  1.04e-04s  5.00e-08d  [Probe] \n",
      "  2.54e-06s  0.00e+00d  [MaxClique] \n",
      "  2.54e-06s  0.00e+00d  [MaxClique] \n",
      "  1.48e-05s  0.00e+00d  [DetectDominanceRelations] \n",
      "  1.48e-05s  0.00e+00d  [DetectDominanceRelations] \n",
      "  7.80e-05s  0.00e+00d  [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1 \n",
      "  7.80e-05s  0.00e+00d  [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1 \n",
      "  7.06e-06s  0.00e+00d  [DetectDuplicateConstraints] \n",
      "  7.06e-06s  0.00e+00d  [DetectDuplicateConstraints] \n",
      "  5.91e-07s  0.00e+00d  [DetectDifferentVariables] \n",
      "  5.91e-07s  0.00e+00d  [DetectDifferentVariables] \n",
      "  1.29e-06s  0.00e+00d  [DetectDominatedLinearConstraints] \n",
      "  1.29e-06s  0.00e+00d  [DetectDominatedLinearConstraints] \n",
      "  1.36e-06s  0.00e+00d  [ProcessSetPPC] \n",
      "  1.36e-06s  0.00e+00d  [ProcessSetPPC] \n",
      "  2.36e-06s  0.00e+00d  [FindAlmostIdenticalLinearConstraints] \n",
      "  2.36e-06s  0.00e+00d  [FindAlmostIdenticalLinearConstraints] \n",
      "  8.92e-07s  0.00e+00d  [FindBigHorizontalLinearOverlap] \n",
      "  8.92e-07s  0.00e+00d  [FindBigHorizontalLinearOverlap] \n",
      "  1.45e-06s  2.40e-07d  [FindBigVerticalLinearOverlap] \n",
      "  1.45e-06s  2.40e-07d  [FindBigVerticalLinearOverlap] \n",
      "  1.27e-06s  0.00e+00d  [MergeClauses] \n",
      "  1.27e-06s  0.00e+00d  [MergeClauses] \n",
      "  7.65e-06s  0.00e+00d  [DetectDominanceRelations] \n",
      "  7.65e-06s  0.00e+00d  [DetectDominanceRelations] \n",
      "  5.26e-05s  0.00e+00d  [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1 \n",
      "  5.26e-05s  0.00e+00d  [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1 \n",
      "\n",
      "Presolve summary:\n",
      "  - 0 affine relations were detected.\n",
      "  - rule 'TODO dual: only one blocking constraint?' was applied 288 times.\n",
      "  - rule 'TODO symmetry: add symmetry breaking inequalities?' was applied 1 time.\n",
      "  - rule 'linear: always true' was applied 48 times.\n",
      "  - rule 'presolve: 0 unused variables removed.' was applied 1 time.\n",
      "  - rule 'presolve: iteration' was applied 1 time.\n",
      "\n",
      "Presolve summary:\n",
      "  - 0 affine relations were detected.\n",
      "  - rule 'TODO dual: only one blocking constraint?' was applied 288 times.\n",
      "  - rule 'TODO symmetry: add symmetry breaking inequalities?' was applied 1 time.\n",
      "  - rule 'linear: always true' was applied 48 times.\n",
      "  - rule 'presolve: 0 unused variables removed.' was applied 1 time.\n",
      "  - rule 'presolve: iteration' was applied 1 time.\n",
      "\n",
      "\n",
      "Presolved satisfaction model '': (model_fingerprint: 0x1e6757375b1bc8ad)\n",
      "#Variables: 48\n",
      "  - 3 in [0,1000]\n",
      "  - 6 in [0,1100]\n",
      "  - 6 in [0,1200]\n",
      "  - 9 in [0,1300]\n",
      "  - 4 in [0,2700]\n",
      "  - 2 in [0,2800]\n",
      "  - 5 in [0,2900]\n",
      "  - 2 in [0,3100]\n",
      "  - 2 in [0,3300]\n",
      "  - 1 in [0,3400]\n",
      "  - 2 in [0,3500]\n",
      "  - 2 in [0,3700]\n",
      "  - 2 in [0,3800]\n",
      "  - 2 in [0,3900]\n",
      "#kInterval: 48\n",
      "#kNoOverlap2D: 1 (#rectangles: 24)\n",
      "Presolved satisfaction model '': (model_fingerprint: 0x1e6757375b1bc8ad)\n",
      "#Variables: 48\n",
      "  - 3 in [0,1000]\n",
      "  - 6 in [0,1100]\n",
      "  - 6 in [0,1200]\n",
      "  - 9 in [0,1300]\n",
      "  - 4 in [0,2700]\n",
      "  - 2 in [0,2800]\n",
      "  - 5 in [0,2900]\n",
      "  - 2 in [0,3100]\n",
      "  - 2 in [0,3300]\n",
      "  - 1 in [0,3400]\n",
      "  - 2 in [0,3500]\n",
      "  - 2 in [0,3700]\n",
      "  - 2 in [0,3800]\n",
      "  - 2 in [0,3900]\n",
      "#kInterval: 48\n",
      "#kNoOverlap2D: 1 (#rectangles: 24)\n",
      "\n",
      "Preloading model.\n",
      "\n",
      "Preloading model.\n",
      "[Symmetry] Graph for symmetry has 193 nodes and 288 arcs.\n",
      "[Symmetry] Graph for symmetry has 193 nodes and 288 arcs.\n",
      "[Symmetry] Symmetry computation done. time: 4.7238e-05 dtime: 5.681e-05\n",
      "[Symmetry] #generators: 3, average support size: 4\n",
      "[Symmetry] Symmetry computation done. time: 4.7238e-05 dtime: 5.681e-05\n",
      "[Symmetry] Found orbitope of size 2 x 2\n",
      "[Symmetry] #generators: 3, average support size: 4\n",
      "[Symmetry] Found orbitope of size 2 x 2\n",
      "#Model   0.00s var:48/48 constraints:49/49\n",
      "#Model   0.00s var:48/48 constraints:49/49\n",
      "\n",
      "\n",
      "Starting search at 0.00s with 16 workers.\n",
      "Starting search at 0.00s with 16 workers.\n",
      "7 full problem subsolvers: [default_lp, max_lp, no_lp, probing, probing_max_lp, quick_restart, quick_restart_no_lp]\n",
      "7 full problem subsolvers: [default_lp, max_lp, no_lp, probing, probing_max_lp, quick_restart, quick_restart_no_lp]\n",
      "8 first solution subsolvers: [fj_long_default, fj_long_lin_default, fj_short_default, fj_short_lin_default, fs_random(2), fs_random_quick_restart(2)]\n",
      "2 incomplete subsolvers: [feasibility_pump, rins/rens]\n",
      "2 helper subsolvers: [neighborhood_helper, synchronization_agent]\n",
      "8 first solution subsolvers: [fj_long_default, fj_long_lin_default, fj_short_default, fj_short_lin_default, fs_random(2), fs_random_quick_restart(2)]\n",
      "2 incomplete subsolvers: [feasibility_pump, rins/rens]\n",
      "2 helper subsolvers: [neighborhood_helper, synchronization_agent]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#1       1.08s probing_max_lp (fixed_bools=0/1664)#1       1.08s probing_max_lp (fixed_bools=0/1664)\n",
      "\n",
      "\n",
      "\n",
      "Task timing                          n [     min,      max]      avg      dev     time         n [     min,      max]      avg      dev    dtime\n",
      "               'default_lp':         1 [   1.09s,    1.09s]    1.09s   0.00ns    1.09s         1 [   1.36s,    1.36s]    1.36s   0.00ns    1.36s\n",
      "         'feasibility_pump':         1 [111.15us, 111.15us] 111.15us   0.00ns 111.15us         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "          'fj_long_default':         6 [ 87.89ms, 295.49ms] 180.38ms  60.56ms    1.08s         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "      'fj_long_lin_default':         6 [119.19ms, 227.08ms] 179.31ms  33.29ms    1.08s         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "         'fj_short_default':         7 [  6.31ms, 178.55ms] 148.84ms  58.45ms    1.04s         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "     'fj_short_lin_default':         6 [ 99.20ms, 273.81ms] 180.28ms  52.71ms    1.08s         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "                'fs_random':         1 [   1.08s,    1.08s]    1.08s   0.00ns    1.08s         1 [306.06ms, 306.06ms] 306.06ms   0.00ns 306.06ms\n",
      "                'fs_random':         1 [   1.08s,    1.08s]    1.08s   0.00ns    1.08s         1 [378.04ms, 378.04ms] 378.04ms   0.00ns 378.04ms\n",
      "  'fs_random_quick_restart':         1 [   1.08s,    1.08s]    1.08s   0.00ns    1.08s         1 [188.93ms, 188.93ms] 188.93ms   0.00ns 188.93ms\n",
      "  'fs_random_quick_restart':         1 [   1.08s,    1.08s]    1.08s   0.00ns    1.08s         1 [215.53ms, 215.53ms] 215.53ms   0.00ns 215.53ms\n",
      "                   'max_lp':         1 [   1.09s,    1.09s]    1.09s   0.00ns    1.09s         1 [908.96ms, 908.96ms] 908.96ms   0.00ns 908.96ms\n",
      "                    'no_lp':         1 [   1.09s,    1.09s]    1.09s   0.00ns    1.09s         1 [   1.28s,    1.28s]    1.28s   0.00ns    1.28s\n",
      "                  'probing':         1 [   1.09s,    1.09s]    1.09s   0.00ns    1.09s         1 [ 99.56ms,  99.56ms]  99.56ms   0.00ns  99.56ms\n",
      "           'probing_max_lp':         1 [   1.09s,    1.09s]    1.09s   0.00ns    1.09s         1 [176.23ms, 176.23ms] 176.23ms   0.00ns 176.23ms\n",
      "            'quick_restart':         1 [   1.09s,    1.09s]    1.09s   0.00ns    1.09s         1 [264.46ms, 264.46ms] 264.46ms   0.00ns 264.46ms\n",
      "      'quick_restart_no_lp':         1 [   1.09s,    1.09s]    1.09s   0.00ns    1.09s         1 [277.03ms, 277.03ms] 277.03ms   0.00ns 277.03ms\n",
      "                'rins/rens':         8 [653.82us, 543.36ms] 138.68ms 180.49ms    1.11s         8 [ 40.00ns, 100.24ms]  43.85ms  46.40ms 350.77ms\n",
      "\n",
      "Task timing                          n [     min,      max]      avg      dev     time         n [     min,      max]      avg      dev    dtime\n",
      "               'default_lp':         1 [   1.09s,    1.09s]    1.09s   0.00ns    1.09s         1 [   1.36s,    1.36s]    1.36s   0.00ns    1.36s\n",
      "         'feasibility_pump':         1 [111.15us, 111.15us] 111.15us   0.00ns 111.15us         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "          'fj_long_default':         6 [ 87.89ms, 295.49ms] 180.38ms  60.56ms    1.08s         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "      'fj_long_lin_default':         6 [119.19ms, 227.08ms] 179.31ms  33.29ms    1.08s         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "         'fj_short_default':         7 [  6.31ms, 178.55ms] 148.84ms  58.45ms    1.04s         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "     'fj_short_lin_default':         6 [ 99.20ms, 273.81ms] 180.28ms  52.71ms    1.08s         0 [  0.00ns,   0.00ns]   0.00ns   0Search stats                   Bools  Conflicts  Branches  Restarts  BoolPropag  IntegerPropag\n",
      "               'default_lp':   6'967      6'957    25'946        33   6'022'558      1'922'792\n",
      "                'fs_random':  10'899     10'423    75'782        23   3'190'805        436'120\n",
      "                'fs_random':  12'925     12'487    56'972        11   2'703'890        304'115\n",
      "  'fs_random_quick_restart':   4'646      4'335   203'530       433   1'339'767        214'189\n",
      "  'fs_random_quick_restart':   5'007      4'750   205'515       475   1'565'027        222'559\n",
      "                   'max_lp':   5'166     10'057    31'978        16   7'497'006        655'231\n",
      "                    'no_lp':   6'731      6'722    23'571        29   5'657'751      1'855'187\n",
      "                  'probing':   3'581      3'824    39'993       294     876'979         92'268\n",
      "           'probing_max_lp':   1'664      1'299     4'199       305     169'126         23'517\n",
      "            'quick_restart':   5'226      5'270   213'195       527   1'963'901        232'199\n",
      "      'quick_restart_no_lp':   5'786      5'363   237'628       536   2'084'897        256'037\n",
      "\n",
      "Lp stats             Component  Iterations  AddedCuts  OPTIMAL  DUAL_F.  DUAL_U.\n",
      "          'max_lp':          1       3'950         25   15'840        1        0\n",
      "  'probing_max_lp':          1       4'812      1'762    4'773       40        0\n",
      "\n",
      ".00ns   0.00ns\n",
      "                'fs_random':         1 [   1.08s,    1.08s]    1.08s   0.00ns    1.08s         1 [306.06ms, 306.06ms] 306.06ms   0.00ns 306.06ms\n",
      "                'fs_random':         1 [   1.08s,    1.08s]    1.08s   0.00ns    1.08s         1 [378.04ms, 378.04ms] 378.04ms   0.00ns 378.04ms\n",
      "  'fs_random_quick_restart':         1 [   1.08s,    1.08s]    1.08s   0.00ns    1.08s         1 [188.93ms, 188.93ms] 188.93ms   0.00ns 188.93ms\n",
      "  'fs_random_quick_restart':         1 [   1.08s,    1.08s]    1.08s   0.00ns    1.08s         1 [215.53ms, 215.53ms] 215.53ms   0.00ns 215.53ms\n",
      "                   'max_lp':         1 [   1.09s,    1.09s]    1.09s   0.00ns    1.09s         1 [908.96ms, 908.96ms] 908.96ms   0.00ns 908.96ms\n",
      "                    'no_lp':         1 [   1.09s,    1.09s]    1.09s   0.00ns    1.09s         1 [   1.28s,    1.28s]    1.28s   0.00ns    1.28s\n",
      "                  'probing':         1 [   1.09s,    1.09s]    1.09s   0.00ns    1.09s         1 [ 99.56ms,  99.56ms]  99.56ms   0.00ns  99.56ms\n",
      "           'probing_max_lp':         1 [   1.09s,    1.09s]    1.09s   0.00ns    1.09s         1 [176.23ms, 176.23ms] 176.23ms   0.00ns 176.23ms\n",
      "            'quick_restart':         1 [   1.09s,    1.09s]    1.09s   0.00ns    1.09s         1 [264.46ms, 264.46ms] 264.46ms   0.00ns 264.46ms\n",
      "      'quick_restart_no_lp':         1 [   1.09s,    1.09s]    1.09s   0.00ns    1.09s         1 [277.03ms, 277.03ms] 277.03ms   0.00ns 277.03ms\n",
      "                'rins/rens':         8 [653.82us, 543.36ms] 138.68ms 180.49ms    1.11s         8 [ 40.00ns, 100.24ms]  43.85ms  46.40ms 350.77ms\n",
      "\n",
      "Search stats                   Bools  Conflicts  Branches  Restarts  BoolPropag  IntegerPropag\n",
      "               'default_lp':   6'967      6'957    25'946        33   6'022'558      1'922'792\n",
      "                'fs_random':  10'899     10'423    75'782        23   3'190'805        436'120\n",
      "                'fs_random':  12'925     12'487    56'972        11   2'703'890        304'115\n",
      "  'fs_random_quick_restart':   4'646      4'335   203'530       433   1'339'767        214'189\n",
      "  'fs_random_quick_restart':   5'007      4'750   205'515       475   1'565'027        222'559\n",
      "                   'max_lp':   5'166     10'057    31'978        16   7'497'006        655'231\n",
      "                    'no_lp':   6'731      6'722    23'571        29   5'657'751      1'855'187\n",
      "                  'probing':   3'581      3'824    39'993       294     876'979         92'268\n",
      "           'probing_max_lp':   1'664      1'299     4'199       305     169'126         23'517\n",
      "            'quick_restart':   5'226      5'270   213'195       527   1'963'901        232'199\n",
      "      'quick_restart_no_lp':   5'786      5'363   237'628       536   2'084'897        256'037\n",
      "\n",
      "Lp stats             Component  Iterations  AddedCuts  OPTIMAL  DUAL_F.  DUAL_U.\n",
      "          'max_lp':          1       3'950         25   15'840        1        0\n",
      "  'probing_max_lp':          1       4'812      1'762    4'773       40        0\n",
      "\n",
      "Lp dLp dimension                                                        Final dimension of first component\n",
      "          'max_lp':      4 rows, 48 columns, 74 entries with magnitude in [8.408964e-01, 1.000000e+00]\n",
      "  'probing_max_lp':  145 rows, 48 columns, 2578 entries with magnitude in [3.277457e-01, 1.000000e+00]\n",
      "\n",
      "imension                                                        Final dimension of first component\n",
      "          'max_lp':      4 rows, 48 columns, 74 entries with magnitude in [8.408964e-01, 1.000000e+00]\n",
      "  'probing_max_lp':  145 rows, 48 columns, 2578 entries with magnitude in [3.277457e-01, 1.000000e+00]\n",
      "\n",
      "Lp debug             CutPropag  CutEqPropag  Adjust  Overflow     Bad  BadScaling\n",
      "          'max_lp':          0            0       0         0      51           0\n",
      "  'probing_max_lp':          0            0       0         0  15'942           0\n",
      "\n",
      "Lp debug             CutPropag  CutEqPropag  Adjust  Overflow     Bad  BadScaling\n",
      "          'max_lp':          0            0       0         0      51           0\n",
      "  'probing_max_lp':          0            0       0         0  15'942           0\n",
      "\n",
      "Lp pool              Constraints  Updates  Simplif  Merged  Shortened  Split  Strenghtened    Cuts/Call\n",
      "          'max_lp':           25        0        0       0          0      0             0        25/32\n",
      "  'probing_max_lp':        1'760        0        0       2          0      0             0  1'762/2'412\n",
      "\n",
      "Lp pool              Constraints  Updates  Simplif  Merged  Shortened  Split  Strenghtened    Cuts/Call\n",
      "          'max_lp':           25        0        0       0          0      0             0        25/32\n",
      "  'probing_max_lp':        1'760        0        0       2          0      0             0  1'762/2'412\n",
      "\n",
      "Lp Cut                               max_lp  probing_max_lp\n",
      "                              CG_K:       1               6\n",
      "                              CG_R:       2             263\n",
      "                           MIR_1_K:       1              23\n",
      "                           MIR_1_R:      10             510\n",
      "        NoOverlap2dXCompletionTime:       5             569\n",
      "        NoOverlap2dYCompletionTime:       5             146\n",
      "  NoOverlap2dYCompletionTimeMirror:       1              11\n",
      "                       ZERO_HALF_K:       -               1\n",
      "                       ZERO_HALF_R:       -             233\n",
      "\n",
      "Lp Cut                               max_lp  probing_max_lp\n",
      "                              CG_K:       1               6\n",
      "                              CG_R:       2             263\n",
      "                           MIR_1_K:       1              23\n",
      "                           MIR_1_R:      10             510\n",
      "        NoOverlap2dXCompletionTime:       5             569\n",
      "        NoOverlap2dYCompletionTime:       5             146\n",
      "  NoOverlap2dYCompletionTimeMirror:       1              11\n",
      "                       ZERO_HALF_K:       -               1\n",
      "                       ZERO_HALF_R:       -             233\n",
      "\n",
      "LNS stats       Improv/Calls  Closed  Difficulty  TimeLimit\n",
      "  'rins/rens':           8/8     50%        0.61       0.10\n",
      "\n",
      "LNS stats       Improv/Calls  Closed  Difficulty  TimeLimit\n",
      "  'rins/rens':           8/8     50%        0.61       0.10\n",
      "\n",
      "LS stats                   Batches  Restarts  LinMoves  GenMoves  CompoundMoves  WeightUpdates\n",
      "       'fj_long_default':        6         1         0     2'507            165              0\n",
      "   'fj_long_lin_default':        6         1         0     1'460              0            307\n",
      "      'fj_short_default':        7         1         0     3'431            147              0\n",
      "  'fj_short_lin_default':        6         1         0     2'497            171              2\n",
      "\n",
      "LS stats                   Batches  Restarts  LinMoves  GenMoves  CompoundMoves  WeightUpdates\n",
      "       'fj_long_default':        6         1         0     2'507            165              0\n",
      "   'fj_long_lin_default':        6         1         0     1'460              0            307\n",
      "      'fj_short_default':        7         1         0     3'431            147              0\n",
      "  'fj_short_lin_default':        6         1         0     2'497            171              2\n",
      "\n",
      "Solution repositories    Added  Queried  Ignored  Synchro\n",
      "  'feasible solutions':      1        0        0        1\n",
      "        'lp solutions':    185        8      130       30\n",
      "                'pump':      0        0\n",
      "\n",
      "Solution repositories    Added  Queried  Ignored  Synchro\n",
      "  'feasible solutions':      1        0        0        1\n",
      "        'lp solutions':    185        8      130       30\n",
      "                'pump':      0        0\n",
      "\n",
      "CpSolverResponse summary:\n",
      "status: OPTIMAL\n",
      "objective: NA\n",
      "best_bound: NA\n",
      "integers: 48\n",
      "booleans: 12925\n",
      "conflicts: 12487\n",
      "branches: 56972\n",
      "propagations: 2703890\n",
      "integer_propagations: 304115\n",
      "restarts: 11\n",
      "lp_iterations: 0\n",
      "walltime: 1.09615\n",
      "usertime: 1.09615\n",
      "deterministic_time: 5.80338\n",
      "gap_integral: 0\n",
      "solution_fingerprint: 0x310bae49568faca5\n",
      "\n",
      "CpSolverResponse summary:\n",
      "status: OPTIMAL\n",
      "objective: NA\n",
      "best_bound: NA\n",
      "integers: 48\n",
      "booleans: 12925\n",
      "conflicts: 12487\n",
      "branches: 56972\n",
      "propagations: 2703890\n",
      "integer_propagations: 304115\n",
      "restarts: 11\n",
      "lp_iterations: 0\n",
      "walltime: 1.09615\n",
      "usertime: 1.09615\n",
      "deterministic_time: 5.80338\n",
      "gap_integral: 0\n",
      "solution_fingerprint: 0x310bae49568faca5\n",
      "\n"
     ]
    }
   ],
   "source": [
    "pack(container, boxes, 100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n",
      "Starting CP-SAT solver v9.8.3296\n",
      "Starting CP-SAT solver v9.8.3296\n",
      "Parameters: log_search_progress: true\n",
      "Parameters: log_search_progress: true\n",
      "Setting number of workers to 16\n",
      "Setting number of workers to 16\n",
      "\n",
      "\n",
      "Initial satisfaction model '': (model_fingerprint: 0x50f40e8ac0ad0a5b)\n",
      "#Variables: 48\n",
      "  - 3 in [0,10000]\n",
      "  - 6 in [0,11000]\n",
      "  - 6 in [0,12000]\n",
      "  - 9 in [0,13000]\n",
      "  - 4 in [0,27000]\n",
      "  - 2 in [0,28000]\n",
      "  - 5 in [0,29000]\n",
      "  - 2 in [0,31000]\n",
      "  - 2 in [0,33000]\n",
      "  - 1 in [0,34000]\n",
      "  - 2 in [0,35000]\n",
      "  - 2 in [0,37000]\n",
      "  - 2 in [0,38000]\n",
      "  - 2 in [0,39000]\n",
      "#kInterval: 48\n",
      "#kLinear1: 48\n",
      "#kNoOverlap2D: 1 (#rectangles: 24)\n",
      "Initial satisfaction model '': (model_fingerprint: 0x50f40e8ac0ad0a5b)\n",
      "#Variables: 48\n",
      "  - 3 in [0,10000]\n",
      "  - 6 in [0,11000]\n",
      "  - 6 in [0,12000]\n",
      "  - 9 in [0,13000]\n",
      "  - 4 in [0,27000]\n",
      "  - 2 in [0,28000]\n",
      "  - 5 in [0,29000]\n",
      "  - 2 in [0,31000]\n",
      "  - 2 in [0,33000]\n",
      "  - 1 in [0,34000]\n",
      "  - 2 in [0,35000]\n",
      "  - 2 in [0,37000]\n",
      "  - 2 in [0,38000]\n",
      "  - 2 in [0,39000]\n",
      "#kInterval: 48\n",
      "#kLinear1: 48\n",
      "#kNoOverlap2D: 1 (#rectangles: 24)\n",
      "\n",
      "Starting presolve at 0.00s\n",
      "\n",
      "Starting presolve at 0.00s\n",
      "  1.38e-05s  0.00e+00d  [DetectDominanceRelations] \n",
      "  1.38e-05s  0.00e+00d  [DetectDominanceRelations] \n",
      "  9.22e-05s  0.00e+00d  [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1 \n",
      "  9.22e-05s  0.00e+00d  [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1 \n",
      "  2.00e-06s  0.00e+00d  [ExtractEncodingFromLinear] \n",
      "  2.00e-06s  0.00e+00d  [ExtractEncodingFromLinear] \n",
      "[Symmetry] Graph for symmetry has 193 nodes and 288 arcs.\n",
      "[Symmetry] Graph for symmetry has 193 nodes and 288 arcs.\n",
      "[Symmetry] Symmetry computation done. time: 5.2268e-05 dtime: 5.681e-05\n",
      "[Symmetry] #generators: 3, average support size: 4\n",
      "[Symmetry] Symmetry computation done. time: 5.2268e-05 dtime: 5.681e-05\n",
      "[Symmetry] 6 orbits with sizes: 2,2,2,2,2,2\n",
      "[Symmetry] Found orbitope of size 2 x 2\n",
      "[Symmetry] #generators: 3, average support size: 4\n",
      "[Symmetry] 6 orbits with sizes: 2,2,2,2,2,2\n",
      "[Symmetry] Found orbitope of size 2 x 2\n",
      "  9.83e-05s  5.00e-08d  [Probe] \n",
      "  9.83e-05s  5.00e-08d  [Probe] \n",
      "  3.41e-06s  0.00e+00d  [MaxClique] \n",
      "  3.41e-06s  0.00e+00d  [MaxClique] \n",
      "  1.46e-05s  0.00e+00d  [DetectDominanceRelations] \n",
      "  1.46e-05s  0.00e+00d  [DetectDominanceRelations] \n",
      "  7.40e-05s  0.00e+00d  [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1 \n",
      "  7.40e-05s  0.00e+00d  [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1 \n",
      "  6.39e-06s  0.00e+00d  [DetectDuplicateConstraints] \n",
      "  6.39e-06s  0.00e+00d  [DetectDuplicateConstraints] \n",
      "  6.62e-07s  0.00e+00d  [DetectDifferentVariables] \n",
      "  6.62e-07s  0.00e+00d  [DetectDifferentVariables] \n",
      "  1.61e-06s  0.00e+00d  [DetectDominatedLinearConstraints] \n",
      "  1.61e-06s  0.00e+00d  [DetectDominatedLinearConstraints] \n",
      "  2.09e-06s  0.00e+00d  [ProcessSetPPC] \n",
      "  2.09e-06s  0.00e+00d  [ProcessSetPPC] \n",
      "  1.36e-06s  0.00e+00d  [FindAlmostIdenticalLinearConstraints] \n",
      "  1.36e-06s  0.00e+00d  [FindAlmostIdenticalLinearConstraints] \n",
      "  8.72e-07s  0.00e+00d  [FindBigHorizontalLinearOverlap] \n",
      "  8.72e-07s  0.00e+00d  [FindBigHorizontalLinearOverlap] \n",
      "  1.14e-06s  2.40e-07d  [FindBigVerticalLinearOverlap] \n",
      "  1.14e-06s  2.40e-07d  [FindBigVerticalLinearOverlap] \n",
      "  1.31e-06s  0.00e+00d  [MergeClauses] \n",
      "  1.31e-06s  0.00e+00d  [MergeClauses] \n",
      "  7.77e-06s  0.00e+00d  [DetectDominanceRelations] \n",
      "  7.77e-06s  0.00e+00d  [DetectDominanceRelations] \n",
      "  5.19e-05s  0.00e+00d  [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1 \n",
      "  5.19e-05s  0.00e+00d  [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1 \n",
      "\n",
      "Presolve summary:\n",
      "  - 0 affine relations were detected.\n",
      "\n",
      "Presolve summary:  - rule 'TODO dual: only one blocking constraint?' was applied 288 times.\n",
      "  - rule 'TODO symmetry: add symmetry breaking inequalities?' was applied 1 time.\n",
      "  - rule 'linear: always true' was applied 48 times.\n",
      "  - rule 'presolve: 0 unused variables removed.' was applied 1 time.\n",
      "\n",
      "  - 0 affine relations were detected.\n",
      "  - rule 'TODO dual: only one blocking constraint?' was applied 288 times.\n",
      "  - rule 'TODO symmetry: add symmetry breaking inequalities?' was applied 1 time.\n",
      "  - rule 'linear: always true' was applied 48 times.\n",
      "  - rule 'presolve: 0 unused variables removed.' was applied 1 time.\n",
      "  - rule 'presolve: iteration' was applied 1 time.\n",
      "  - rule 'presolve: iteration' was applied 1 time.\n",
      "\n",
      "\n",
      "Presolved satisfaction model '': (model_fingerprint: 0x413a5366acad63cb)\n",
      "#Variables: 48\n",
      "  - 3 in [0,10000]\n",
      "  - 6 in [0,11000]\n",
      "  - 6 in [0,12000]\n",
      "  - 9 in [0,13000]\n",
      "  - 4 in [0,27000]\n",
      "  - 2 in [0,28000]\n",
      "  - 5 in [0,29000]\n",
      "  - 2 in [0,31000]\n",
      "  - 2 in [0,33000]\n",
      "  - 1 in [0,34000]\n",
      "  - 2 in [0,35000]\n",
      "  - 2 in [0,37000]\n",
      "  - 2 in [0,38000]\n",
      "  - 2 in [0,39000]\n",
      "#kInterval: 48\n",
      "#kNoOverlap2D: 1 (#rectangles: 24)Presolved satisfaction model '': (model_fingerprint: 0x413a5366acad63cb)\n",
      "#Variables: 48\n",
      "  - 3 in [0,10000]\n",
      "  - 6 in [0,11000]\n",
      "  - 6 in [0,12000]\n",
      "  - 9 in [0,13000]\n",
      "  - 4 in [0,27000]\n",
      "  - 2 in [0,28000]\n",
      "  - 5 in [0,29000]\n",
      "  - 2 in [0,31000]\n",
      "  - 2 in [0,33000]\n",
      "  - 1 in [0,34000]\n",
      "  - 2 in [0,35000]\n",
      "  - 2 in [0,37000]\n",
      "  - 2 in [0,38000]\n",
      "  - 2 in [0,39000]\n",
      "#kInterval: 48\n",
      "#kNoOverlap2D: 1 (#rectangles: 24)\n",
      "\n",
      "Preloading model.\n",
      "\n",
      "\n",
      "Preloading model.\n",
      "[Symmetry] Graph for symmetry has 193 nodes and 288 arcs.\n",
      "[Symmetry] Graph for symmetry has 193 nodes and 288 arcs.\n",
      "[Symmetry] Symmetry computation done. time: 5.1436e-05 dtime: 5.681e-05\n",
      "[Symmetry] Symmetry computation done. time: 5.1436e-05 dtime: 5.681e-05\n",
      "[Symmetry] #generators: 3, average support size: 4\n",
      "[Symmetry] #generators: 3, average support size: 4\n",
      "[Symmetry] Found orbitope of size 2 x 2\n",
      "[Symmetry] Found orbitope of size 2 x 2\n",
      "#Model   0.00s var:48/48 constraints:49/49\n",
      "#Model   0.00s var:48/48 constraints:49/49\n",
      "\n",
      "\n",
      "Starting search at 0.00s with 16 workers.\n",
      "Starting search at 0.00s with 16 workers.\n",
      "7 full problem subsolvers: [default_lp, max_lp, no_lp, probing, probing_max_lp, quick_restart, quick_restart_no_lp]\n",
      "7 full problem subsolvers: [default_lp, max_lp, no_lp, probing, probing_max_lp, quick_restart, quick_restart_no_lp]\n",
      "8 first solution subsolvers: [fj_long_default, fj_long_lin_default, fj_short_default, fj_short_lin_default, fs_random(2), fs_random_quick_restart(2)]\n",
      "8 first solution subsolvers: [fj_long_default, fj_long_lin_default, fj_short_default, fj_short_lin_default, fs_random(2), fs_random_quick_restart(2)]\n",
      "2 incomplete subsolvers: [feasibility_pump, rins/rens]\n",
      "2 helper subsolvers: [neighborhood_helper, synchronization_agent]\n",
      "2 incomplete subsolvers: [feasibility_pump, rins/rens]\n",
      "2 helper subsolvers: [neighborhood_helper, synchronization_agent]\n",
      "#1      40.28s probing_max_lp (fixed_bools=0/8381)\n",
      "#1      40.28s probing_max_lp (fixed_bools=0/8381)\n",
      "\n",
      "\n",
      "Task timing                          n [     min,      max]      avg      dev     time         n [     min,      max]      avg      dev    dtime\n",
      "               'default_lp':         1 [  40.32s,   40.32s]   40.32s   0.00ns   40.32s         1 [  39.93s,   39.93s]   39.93s   0.00ns   39.93s\n",
      "         'feasibility_pump':         1 [122.58us, 122.58us] 122.58us   0.00ns 122.58us         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "          'fj_long_default':       129 [ 68.69ms, 232.16ms] 169.12ms  18.84ms   21.82s         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "      'fj_long_lin_default':       128 [150.17ms, 279.89ms] 170.16ms  18.57ms   21.78s         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "         'fj_short_default':       129 [146.20ms, 285.04ms] 176.34ms  25.17ms   22.75s         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "     'fj_short_lin_default':       128 [148.38ms, 250.16ms] 171.60ms  18.06ms   21.96s         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "                'fs_random':         1 [  40.27s,   40.27s]   40.27s   0.00ns   40.27s         1 [  23.01s,   23.01s]   23.01s   0.00ns   23.01s\n",
      "                'fs_random':         1 [  40.27s,   40.27s]   40.27s   0.00ns   40.27s         1 [  27.31s,   27.31s]   27.31s   0.00ns   27.31s\n",
      "  'fs_random_quick_restart':         1 [  40.27s,   40.27s]   40.27s   0.00ns   40.27s         1 [  12.41s,   12.41s]   12.41s   0.00ns   12.41s\n",
      "  'fs_random_quick_restart':         1 [  40.27s,   40.27s]   40.27s   0.00ns   40.27s         1 [  13.35s,   13.35s]   13.35s   0.00ns   13.35s\n",
      "                   'max_lp':         1 [  40.32s,   40.32s]   40.32s   0.00ns   40.32s         1 [  42.63s,   42.63s]   42.63s   0.00ns   42.63s\n",
      "                    'no_lp':         1 [  40.32s,   40.32s]   40.32s   0.00ns   40.32s         1 [  38.09s,   38.09s]   38.09s   0.00ns   38.09s\n",
      "                  'probing':         1 [  40.32s,   40.32s]   40.32s   0.00ns   40.32s         1 [   7.50s,    7.50s]    7.50s   0.00ns    7.50s\n",
      "           'probing_max_lp':         1 [  40.32s,   40.32s]   40.32s   0.00ns   40.32s         1 [  10.55s,   10.55s]   10.55s   0.00ns   10.55s\n",
      "            'quick_restart':         1 [  40.32s,   40.32s]   40.32s   0.00ns   40.32s         1 [  11.70s,   11.70s]   11.70s   0.00ns   11.70s\n",
      "      'quick_restart_no_lp':         1 [  40.32s,   40.32s]   40.32s   0.00ns   40.32s         1 [  12.41s,   12.41s]   12.41s   0.00ns   12.41s\n",
      "                'rins/rens':       129 [593.78us,   20.90s] 876.60ms    2.51s    1.88m       126 [ 40.00ns, 102.75ms]  50.63ms  50.08ms    6.38s\n",
      "\n",
      "Task timing                          n [     min,      max]      avg      dev     time         n [     min,      max]      avg      dev    dtime\n",
      "               'default_lp':         1 [  40.32s,   40.32s]   40.32s   0.00ns   40.32s         1 [  39.93s,   39.93s]   39.93s   0.00ns   39.93s\n",
      "         'feasibility_pump':         1 [122.58us, 122.58us] 122.58us   0.00ns 122.58us         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "          'fj_long_default':       129 [ 68.69ms, 232.16ms] 169.12ms  18.84ms   21.82s         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "      'fj_long_lin_default':       128 [150.17ms, 279.89ms] 170.16ms  18.57ms   21.78s         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "         'fj_short_default':       129 [146.20ms, 285.04ms] 176.34ms  25.17ms   22.75s         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "     'fj_short_lin_default':       128 [148.38ms, 250.16ms] 171.60ms  18.06ms   21.96s         0 [  0.00ns,   0.00ns]   0.00ns   0Search stats                    Bools  Conflicts   Branches  Restarts   BoolPropag  IntegerPropag\n",
      "               'default_lp':   45'050     45'034    269'896         7  368'842'514     55'803'564\n",
      "                'fs_random':  101'918    105'101  1'059'894        47  243'088'353     28'222'990\n",
      "                'fs_random':   83'561     81'791    177'551         5  180'019'000        299'129\n",
      "  'fs_random_quick_restart':   37'320     42'291  6'120'870     4'227  114'771'045      6'324'790\n",
      "  'fs_random_quick_restart':   37'772     40'950  6'221'024     4'095  106'623'075      6'430'384\n",
      "                   'max_lp':   74'175    120'540    324'162        87  368'893'572     21'707'812\n",
      "                    'no_lp':   44'121     44'105    251'675         7  348'418'994     55'784'414\n",
      "                  'probing':   85'994     91'971    948'836     3'402   72'254'823      2'127'263\n",
      "           'probing_max_lp':    8'381     10'172     41'166     3'497    8'783'929        227'191\n",
      "            'quick_restart':   35'934     39'514  6'556'329     3'951   98'213'296      6'775'664\n",
      "      'quick_restart_no_lp':   36'691     40'369  5'923'387     4'036  106'099'189      6'193'081\n",
      "\n",
      ".00ns   0.00ns\n",
      "                'fs_random':         1 [  40.27s,   40.27s]   40.27s   0.00ns   40.27s         1 [  23.01s,   23.01s]   23.01s   0.00ns   23.01s\n",
      "                'fs_random':         1 [  40.27s,   40.27s]   40.27s   0.00ns   40.27s         1 [  27.31s,   27.31s]   27.31s   0.00ns   27.31s\n",
      "  'fs_random_quick_restart':         1 [  40.27s,   40.27s]   40.27s   0.00ns   40.27s         1 [  12.41s,   12.41s]   12.41s   0.00ns   12.41s\n",
      "  'fs_random_quick_restart':         1 [  40.27s,   40.27s]   40.27s   0.00ns   40.27s         1 [  13.35s,   13.35s]   13.35s   0.00ns   13.35s\n",
      "                   'max_lp':         1 [  40.32s,   40.32s]   40.32s   0.00ns   40.32s         1 [  42.63s,   42.63s]   42.63s   0.00ns   42.63s\n",
      "                    'no_lp':         1 [  40.32s,   40.32s]   40.32s   0.00ns   40.32s         1 [  38.09s,   38.09s]   38.09s   0.00ns   38.09s\n",
      "                  'probing':         1 [  40.32s,   40.32s]   40.32s   0.00ns   40.32s         1 [   7.50s,    7.50s]    7.50s   0.00ns    7.50s\n",
      "           'probing_max_lp':         1 [  40.32s,   40.32s]   40.32s   0.00ns   40.32s         1 [  10.55s,   10.55s]   10.55s   0.00ns   10.55s\n",
      "            'quick_restart':         1 [  40.32s,   40.32s]   40.32s   0.00ns   40.32s         1 [  11.70s,   11.70s]   11.70s   0.00ns   11.70s\n",
      "      'quick_restart_no_lp':         1 [  40.32s,   40.32s]   40.32s   0.00ns   40.32s         1 [  12.41s,   12.41s]   12.41s   0.00ns   12.41s\n",
      "                'rins/rens':       129 [593.78us,   20.90s] 876.60ms    2.51s    1.88m       126 [ 40.00ns, 102.75ms]  50.63ms  50.08ms    6.38s\n",
      "\n",
      "Search stats                    Bools  Conflicts   Branches  Restarts   BoolPropag  IntegerPropag\n",
      "               'default_lp':   45'050     45'034    269'896         7  368'842'514     55'803'564\n",
      "                'fs_random':  101'918    105'101  1'059'894        47  243'088'353     28'222'990\n",
      "                'fs_random':   83'561     81'791    177'551         5  180'019'000        299'129\n",
      "  'fs_random_quick_restart':   37'320     42'291  6'120'870     4'227  114'771'045      6'324'790\n",
      "  'fs_random_quick_restart':   37'772     40'950  6'221'024     4'095  106'623'075      6'430'384\n",
      "                   'max_lp':   74'175    120'540    324'162        87  368'893'572     21'707'812\n",
      "                    'no_lp':   44'121     44'105    251'675         7  348'418'994     55'784'414\n",
      "                  'probing':   85'994     91'971    948'836     3'402   72'254'823      2'127'263\n",
      "           'probing_max_lp':    8'381     10'172     41'166     3'497    8'783'929        227'191\n",
      "            'quick_restart':   35'934     39'514  6'556'329     3'951   98'213'296      6'775'664\n",
      "      'quick_restart_no_lp':   36'691     40'369  5'923'387     4'036  106'099'189      6'193'081\n",
      "\n",
      "Lp stats             Component  Iterations  AddedCuts  OPTIMAL  DUAL_F.  DUAL_U.\n",
      "          'max_lp':          1      17'892         22  222'852        1        0\n",
      "  'probing_max_lp':          1      62'920     18'683   50'700      492        0\n",
      "\n",
      "Lp stats             Component  Iterations  AddedCuts  OPTIMAL  DUAL_F.  DUAL_U.\n",
      "          'max_lp':          1      17'892         22  222'852        1        0\n",
      "  'probing_max_lp':          1      62'920     18'683   50'700      492        0\n",
      "\n",
      "Lp dimension                                                        Final dimension of first component\n",
      "          'max_lp':      4 rows, 48 columns, 80 entries with magnitude in [6.948003e-01, 1.000000e+00]\n",
      "  'probing_max_lp':  201 rows, 48 columns, 3558 entries with magnitude in [2.379367e-01, 1.000000e+00]\n",
      "\n",
      "Lp dimension                                                        Final dimension of first component\n",
      "          'max_lp':      4 rows, 48 columns, 80 entries with magnitude in [6.948003e-01, 1.000000e+00]\n",
      "  'probing_max_lp':  201 rows, 48 columns, 3558 entries with magnitude in [2.379367e-01, 1.000000e+00]\n",
      "\n",
      "Lp debug             CutPropag  CutEqPropag  Adjust  Overflow      Bad  BadScaling\n",
      "          'max_lp':          0            0       0         0       38           0\n",
      "  'probing_max_lp':          0            0       0         0  176'974           0\n",
      "\n",
      "Lp debug             CutPropag  CutEqPropag  Adjust  Overflow      Bad  BadScaling\n",
      "          'max_lp':          0            0       0         0       38           0\n",
      "  'probing_max_lp':          0            0       0         0  176'974           0\n",
      "\n",
      "Lp pool              Constraints  Updates  Simplif  Merged  Shortened  Split  Strenghtened      Cuts/Call\n",
      "          'max_lp':           22        0        0       0          0      0             0          22/28\n",
      "  'probing_max_lp':        9'652        0        0      31          0      0             1  18'683/26'552\n",
      "\n",
      "Lp pool              Constraints  Updates  Simplif  Merged  Shortened  Split  Strenghtened      Cuts/Call\n",
      "          'max_lp':           22        0        0       0          0      0             0          22/28\n",
      "  'probing_max_lp':        9'652        0        0      31          0      0             1  18'683/26'552\n",
      "\n",
      "Lp Cut                               max_lp  probing_max_lp\n",
      "                             CG_FF:       -               6\n",
      "                              CG_K:       1             111\n",
      "                              CG_R:       2           2'654\n",
      "                           MIR_1_K:       1             278\n",
      "                           MIR_1_R:       8           5'555\n",
      "                           MIR_2_K:       -               2\n",
      "                           MIR_2_R:       -              12\n",
      "        NoOverlap2dXCompletionTime:       5           4'934\n",
      "  NoOverlap2dXCompletionTimeMirror:       -               1\n",
      "        NoOverlap2dYCompletionTime:       5           2'657\n",
      "  NoOverlap2dYCompletionTimeMirror:       -             189\n",
      "                       ZERO_HALF_K:       -               3\n",
      "                       ZERO_HALF_R:       -           2'281\n",
      "\n",
      "Lp Cut                               max_lp  probing_max_lp\n",
      "                             CG_FF:       -               6\n",
      "                              CG_K:       1             111\n",
      "                              CG_R:       2           2'654\n",
      "                           MIR_1_K:       1             278\n",
      "                           MIR_1_R:       8           5'555\n",
      "                           MIR_2_K:       -               2\n",
      "                           MIR_2_R:       -              12\n",
      "        NoOverlap2dXCompletionTime:       5           4'934\n",
      "  NoOverlap2dXCompletionTimeMirror:       -               1\n",
      "        NoOverlap2dYCompletionTime:       5           2'657\n",
      "  NoOverlap2dYCompletionTimeMirror:       -             189\n",
      "                       ZERO_HALF_K:       -               3\n",
      "                       ZERO_HALF_R:       -           2'281\n",
      "\n",
      "LNS stats       Improv/Calls  Closed  Difficulty  TimeLimit\n",
      "  'rins/rens':       129/129     49%        0.63       0.10\n",
      "\n",
      "LNS stats       Improv/Calls  Closed  Difficulty  TimeLimit\n",
      "  'rins/rens':       129/129     49%        0.63       0.10\n",
      "\n",
      "LS stats                   Batches  Restarts  LinMoves  GenMoves  CompoundMoves  WeightUpdates\n",
      "       'fj_long_default':      129         1         0    48'190          1'264             26\n",
      "   'fj_long_lin_default':      128         1         0    11'141              0         12'153\n",
      "      'fj_short_default':      129         1         0    78'736            834            127\n",
      "  'fj_short_lin_default':      128         1         0    50'869            793             35\n",
      "\n",
      "LS stats                   Batches  Restarts  LinMoves  GenMoves  CompoundMoves  WeightUpdates\n",
      "       'fj_long_default':      129         1         0    48'190          1'264             26\n",
      "   'fj_long_lin_default':      128         1         0    11'141              0         12'153\n",
      "      'fj_short_default':      129         1         0    78'736            834            127\n",
      "  'fj_short_lin_default':      128         1         0    50'869            793             35\n",
      "\n",
      "Solution repositories    Added  Queried  Ignored  Synchro\n",
      "  'feasible solutions':      1        0        0        1\n",
      "        'lp solutions':  2'567      129      639      631\n",
      "                'pump':      0        0\n",
      "\n",
      "Solution repositories    Added  Queried  Ignored  Synchro\n",
      "  'feasible solutions':      1        0        0        1\n",
      "        'lp solutions':  2'567      129      639      631\n",
      "                'pump':      0        0\n",
      "\n",
      "CpSolverResponse summary:\n",
      "status: OPTIMAL\n",
      "objective: NA\n",
      "best_bound: NA\n",
      "integers: 48\n",
      "booleans: 83561\n",
      "conflicts: 81791\n",
      "branches: 177551\n",
      "propagations: 180019000\n",
      "integer_propagations: 299129\n",
      "restarts: 5\n",
      "lp_iterations: 0\n",
      "walltime: 40.3613\n",
      "usertime: 40.3613\n",
      "deterministic_time: 245.259\n",
      "gap_integral: 0\n",
      "solution_fingerprint: 0xc40e733b726ac811\n",
      "\n",
      "CpSolverResponse summary:\n",
      "status: OPTIMAL\n",
      "objective: NA\n",
      "best_bound: NA\n",
      "integers: 48\n",
      "booleans: 83561\n",
      "conflicts: 81791\n",
      "branches: 177551\n",
      "propagations: 180019000\n",
      "integer_propagations: 299129\n",
      "restarts: 5\n",
      "lp_iterations: 0\n",
      "walltime: 40.3613\n",
      "usertime: 40.3613\n",
      "deterministic_time: 245.259\n",
      "gap_integral: 0\n",
      "solution_fingerprint: 0xc40e733b726ac811\n",
      "\n"
     ]
    }
   ],
   "source": [
    "pack(container, boxes, 1000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Starting CP-SAT solver v9.8.3296\n",
      "\n",
      "Parameters: log_search_progress: true\n",
      "Starting CP-SAT solver v9.8.3296\n",
      "Parameters: log_search_progress: true\n",
      "Setting number of workers to 16\n",
      "Setting number of workers to 16\n",
      "\n",
      "\n",
      "Initial satisfaction model '': (model_fingerprint: 0x758d3d7aad74b155)\n",
      "#Variables: 48\n",
      "  - 3 in [0,100000]\n",
      "  - 6 in [0,110000]\n",
      "  - 6 in [0,120000]\n",
      "  - 9 in [0,130000]\n",
      "  - 4 in [0,270000]\n",
      "  - 2 in [0,280000]\n",
      "  - 5 in [0,290000]\n",
      "  - 2 in [0,310000]\n",
      "  - 2 in [0,330000]\n",
      "  - 1 in [0,340000]\n",
      "  - 2 in [0,350000]\n",
      "  - 2 in [0,370000]\n",
      "  - 2 in [0,380000]\n",
      "  - 2 in [0,390000]\n",
      "#kInterval: 48\n",
      "#kLinear1: 48\n",
      "#kNoOverlap2D: 1 (#rectangles: 24)\n",
      "\n",
      "Initial satisfaction model '': (model_fingerprint: 0x758d3d7aad74b155)\n",
      "#Variables: 48\n",
      "  - 3 in [0,100000]\n",
      "  - 6 in [0,110000]\n",
      "  - 6 in [0,120000]\n",
      "  - 9 in [0,130000]\n",
      "  - 4 in [0,270000]\n",
      "  - 2 in [0,280000]\n",
      "  - 5 in [0,290000]\n",
      "  - 2 in [0,310000]\n",
      "  - 2 in [0,330000]\n",
      "  - 1 in [0,340000]\n",
      "  - 2 in [0,350000]\n",
      "  - 2 in [0,370000]\n",
      "  - 2 in [0,380000]\n",
      "  - 2 in [0,390000]\n",
      "#kInterval: 48\n",
      "#kLinear1: 48\n",
      "#kNoOverlap2D: 1 (#rectangles: 24)\n",
      "\n",
      "Starting presolve at 0.00s\n",
      "Starting presolve at 0.00s\n",
      "  1.51e-05s  0.00e+00d  [DetectDominanceRelations] \n",
      "  1.51e-05s  0.00e+00d  [DetectDominanceRelations] \n",
      "  1.02e-04s  0.00e+00d  [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1 \n",
      "  1.02e-04s  0.00e+00d  [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1 \n",
      "  2.81e-06s  0.00e+00d  [ExtractEncodingFromLinear] \n",
      "  2.81e-06s  0.00e+00d  [ExtractEncodingFromLinear] \n",
      "[Symmetry] Graph for symmetry has 193 nodes and 288 arcs.\n",
      "[Symmetry] Graph for symmetry has 193 nodes and 288 arcs.\n",
      "[Symmetry] Symmetry computation done. time: 5.4742e-05 dtime: 5.681e-05\n",
      "[Symmetry] #generators: 3, average support size: 4\n",
      "[Symmetry] Symmetry computation done. time: 5.4742e-05 dtime: 5.681e-05\n",
      "[Symmetry] 6 orbits with sizes: 2,2,2,2,2,2\n",
      "[Symmetry] Found orbitope of size 2 x 2\n",
      "[Symmetry] #generators: 3, average support size: 4\n",
      "[Symmetry] 6 orbits with sizes: 2,2,2,2,2,2\n",
      "[Symmetry] Found orbitope of size 2 x 2\n",
      "  9.73e-05s  5.00e-08d  [Probe] \n",
      "  9.73e-05s  5.00e-08d  [Probe] \n",
      "  2.20e-06s  0.00e+00d  [MaxClique] \n",
      "  2.20e-06s  0.00e+00d  [MaxClique] \n",
      "  1.93e-05s  0.00e+00d  [DetectDominanceRelations] \n",
      "  1.93e-05s  0.00e+00d  [DetectDominanceRelations] \n",
      "  9.31e-05s  0.00e+00d  [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1 \n",
      "  9.31e-05s  0.00e+00d  [PresolveToFixPoint] #num_loops=2 #num_dual_strengthening=1 \n",
      "  9.83e-06s  0.00e+00d  [DetectDuplicateConstraints] \n",
      "  9.83e-06s  0.00e+00d  [DetectDuplicateConstraints] \n",
      "  8.11e-07s  0.00e+00d  [DetectDifferentVariables] \n",
      "  8.11e-07s  0.00e+00d  [DetectDifferentVariables] \n",
      "  1.22e-06s  0.00e+00d  [DetectDominatedLinearConstraints] \n",
      "  1.22e-06s  0.00e+00d  [DetectDominatedLinearConstraints] \n",
      "  1.61e-06s  0.00e+00d  [ProcessSetPPC] \n",
      "  1.47e-06s  0.00e+00d  [FindAlmostIdenticalLinearConstraints] \n",
      "  9.22e-07s  0.00e+00d  [FindBigHorizontalLinearOverlap] \n",
      "  1.10e-06s  2.40e-07d  [FindBigVerticalLinearOverlap] \n",
      "  1.26e-06s  0.00e+00d  [MergeClauses] \n",
      "  1.61e-06s  0.00e+00d  [ProcessSetPPC] \n",
      "  1.47e-06s  0.00e+00d  [FindAlmostIdenticalLinearConstraints] \n",
      "  9.22e-07s  0.00e+00d  [FindBigHorizontalLinearOverlap] \n",
      "  1.10e-06s  2.40e-07d  [FindBigVerticalLinearOverlap] \n",
      "  1.26e-06s  0.00e+00d  [MergeClauses] \n",
      "  7.87e-06s  0.00e+00d  [DetectDominanceRelations] \n",
      "  7.87e-06s  0.00e+00d  [DetectDominanceRelations] \n",
      "  5.23e-05s  0.00e+00d  [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1 \n",
      "  5.23e-05s  0.00e+00d  [PresolveToFixPoint] #num_loops=1 #num_dual_strengthening=1 \n",
      "\n",
      "\n",
      "Presolve summary:\n",
      "Presolve summary:\n",
      "  - 0 affine relations were detected.\n",
      "  - 0 affine relations were detected.\n",
      "  - rule 'TODO dual: only one blocking constraint?' was applied 288 times.\n",
      "  - rule 'TODO symmetry: add symmetry breaking inequalities?' was applied 1 time.\n",
      "  - rule 'linear: always true' was applied 48 times.\n",
      "  - rule 'presolve: 0 unused variables removed.' was applied 1 time.\n",
      "  - rule 'presolve: iteration' was applied 1 time.\n",
      "  - rule 'TODO dual: only one blocking constraint?' was applied 288 times.\n",
      "  - rule 'TODO symmetry: add symmetry breaking inequalities?' was applied 1 time.\n",
      "  - rule 'linear: always true' was applied 48 times.\n",
      "  - rule 'presolve: 0 unused variables removed.' was applied 1 time.\n",
      "  - rule 'presolve: iteration' was applied 1 time.\n",
      "\n",
      "\n",
      "Presolved satisfaction model '': (model_fingerprint: 0xa818096634ddbdfe)\n",
      "#Variables: 48\n",
      "  - 3 in [0,100000]\n",
      "  - 6 in [0,110000]\n",
      "  - 6 in [0,120000]\n",
      "  - 9 in [0,130000]\n",
      "  - 4 in [0,270000]\n",
      "  - 2 in [0,280000]\n",
      "  - 5 in [0,290000]\n",
      "  - 2 in [0,310000]\n",
      "  - 2 in [0,330000]\n",
      "  - 1 in [0,340000]\n",
      "  - 2 in [0,350000]\n",
      "  - 2 in [0,370000]\n",
      "  - 2 in [0,380000]\n",
      "  - 2 in [0,390000]\n",
      "#kInterval: 48\n",
      "#kNoOverlap2D: 1 (#rectangles: 24)\n",
      "Presolved satisfaction model '': (model_fingerprint: 0xa818096634ddbdfe)\n",
      "#Variables: 48\n",
      "  - 3 in [0,100000]\n",
      "  - 6 in [0,110000]\n",
      "  - 6 in [0,120000]\n",
      "  - 9 in [0,130000]\n",
      "  - 4 in [0,270000]\n",
      "  - 2 in [0,280000]\n",
      "  - 5 in [0,290000]\n",
      "  - 2 in [0,310000]\n",
      "  - 2 in [0,330000]\n",
      "  - 1 in [0,340000]\n",
      "  - 2 in [0,350000]\n",
      "  - 2 in [0,370000]\n",
      "  - 2 in [0,380000]\n",
      "  - 2 in [0,390000]\n",
      "#kInterval: 48\n",
      "#kNoOverlap2D: 1 (#rectangles: 24)\n",
      "\n",
      "Preloading model.\n",
      "\n",
      "Preloading model.\n",
      "[Symmetry] Graph for symmetry has 193 nodes and 288 arcs.\n",
      "[Symmetry] Graph for symmetry has 193 nodes and 288 arcs.\n",
      "[Symmetry] Symmetry computation done. time: 5.0083e-05 dtime: 5.681e-05\n",
      "[Symmetry] #generators: 3, average support size: 4\n",
      "[Symmetry] Symmetry computation done. time: 5.0083e-05 dtime: 5.681e-05\n",
      "[Symmetry] Found orbitope of size 2 x 2\n",
      "[Symmetry] #generators: 3, average support size: 4\n",
      "[Symmetry] Found orbitope of size 2 x 2\n",
      "#Model   0.00s var:48/48 constraints:49/49\n",
      "#Model   0.00s var:48/48 constraints:49/49\n",
      "\n",
      "\n",
      "Starting search at 0.00s with 16 workers.\n",
      "Starting search at 0.00s with 16 workers.\n",
      "7 full problem subsolvers: [default_lp, max_lp, no_lp, probing, probing_max_lp, quick_restart, quick_restart_no_lp]\n",
      "7 full problem subsolvers: [default_lp, max_lp, no_lp, probing, probing_max_lp, quick_restart, quick_restart_no_lp]\n",
      "8 first solution subsolvers: [fj_long_default, fj_long_lin_default, fj_short_default, fj_short_lin_default, fs_random(2), fs_random_quick_restart(2)]\n",
      "8 first solution subsolvers: [fj_long_default, fj_long_lin_default, fj_short_default, fj_short_lin_default, fs_random(2), fs_random_quick_restart(2)]\n",
      "2 incomplete subsolvers: [feasibility_pump, rins/rens]\n",
      "2 incomplete subsolvers: [feasibility_pump, rins/rens]\n",
      "2 helper subsolvers: [neighborhood_helper, synchronization_agent]\n",
      "2 helper subsolvers: [neighborhood_helper, synchronization_agent]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#1       0.37s probing_max_lp (fixed_bools=0/3616)\n",
      "#1       0.37s probing_max_lp (fixed_bools=0/3616)\n",
      "#2       0.38s quick_restart (fixed_bools=0/2211)\n",
      "#2       0.38s quick_restart (fixed_bools=0/2211)\n",
      "\n",
      "\n",
      "Task timing                          n [     min,      max]      avg      dev     time         n [     min,      max]      avg      dev    dtime\n",
      "               'default_lp':         1 [373.23ms, 373.23ms] 373.23ms   0.00ns 373.23ms         1 [ 51.22ms,  51.22ms]  51.22ms   0.00ns  51.22ms\n",
      "         'feasibility_pump':         1 [ 88.72us,  88.72us]  88.72us   0.00ns  88.72us         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "          'fj_long_default':         2 [ 50.75ms, 321.99ms] 186.37ms 135.62ms 372.74ms         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "      'fj_long_lin_default':         2 [119.85ms, 240.72ms] 180.28ms  60.44ms 360.56ms         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "         'fj_short_default':         3 [ 38.97ms, 168.77ms] 121.42ms  58.51ms 364.25ms         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "     'fj_short_lin_default':         2 [128.52ms, 232.31ms] 180.41ms  51.90ms 360.83ms         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "                'fs_random':         1 [361.35ms, 361.35ms] 361.35ms   0.00ns 361.35ms         1 [  6.39ms,   6.39ms]   6.39ms   0.00ns   6.39ms\n",
      "                'fs_random':         1 [362.54ms, 362.54ms] 362.54ms   0.00ns 362.54ms         1 [ 36.32ms,  36.32ms]  36.32ms   0.00ns  36.32ms\n",
      "  'fs_random_quick_restart':         1 [361.32ms, 361.32ms] 361.32ms   0.00ns 361.32ms         1 [ 86.37ms,  86.37ms]  86.37ms   0.00ns  86.37ms\n",
      "  'fs_random_quick_restart':         1 [361.36ms, 361.36ms] 361.36ms   0.00ns 361.36ms         1 [ 74.13ms,  74.13ms]  74.13ms   0.00ns  74.13ms\n",
      "                   'max_lp':         1 [373.34ms, 373.34ms] 373.34ms   0.00ns 373.34ms         1 [ 23.89ms,  23.89ms]  23.89ms   0.00ns  23.89ms\n",
      "                    'no_lp':         1 [373.25ms, 373.25ms] 373.25ms   0.00ns 373.25ms         1 [ 59.43ms,  59.43ms]  59.43ms   0.00ns  59.43ms\n",
      "                  'probing':         1 [373.33ms, 373.33ms] 373.33ms   0.00ns 373.33ms         1 [ 39.32ms,  39.32ms]  39.32ms   0.00ns  39.32ms\n",
      "           'probing_max_lp':         1 [373.41ms, 373.41ms] 373.41ms   0.00ns 373.41ms         1 [ 24.63ms,  24.63ms]  24.63ms   0.00ns  24.63ms\n",
      "            'quick_restart':         1 [373.09ms, 373.09ms] 373.09ms   0.00ns 373.09ms         1 [ 56.44ms,  56.44ms]  56.44ms   0.00ns  56.44ms\n",
      "      'quick_restart_no_lp':         1 [373.06ms, 373.06ms] 373.06ms   0.00ns 373.06ms         1 [ 71.01ms,  71.01ms]  71.01ms   0.00ns  71.01ms\n",
      "                'rins/rens':         4 [611.59us, 354.58ms]  89.15ms 153.25ms 356.62ms         4 [ 40.00ns,   3.74ms] 935.30us   1.62ms   3.74ms\n",
      "\n",
      "Task timing                          n [     min,      max]      avg      dev     time         n [     min,      max]      avg      dev    dtime\n",
      "               'default_lp':         1 [373.23ms, 373.23ms] 373.23ms   0.00ns 373.23ms         1 [ 51.22ms,  51.22ms]  51.22ms   0.00ns  51.22ms\n",
      "         'feasibility_pump':         1 [ 88.72us,  88.72us]  88.72us   0.00ns  88.72us         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "          'fj_long_default':         2 [ 50.75ms, 321.99ms] 186.37ms 135.62ms 372.74ms         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "      'fj_long_lin_default':         2 [119.85ms, 240.72ms] 180.28ms  60.44ms 360.56ms         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "         'fj_short_default':         3 [ 38.97ms, 168.77ms] 121.42ms  58.51ms 364.25ms         0 [  0.00ns,   0.00ns]   0.00ns   0.00ns   0.00ns\n",
      "     'fj_short_lin_default':         2 [128.52ms, 232.31ms] 180.41ms  51.90ms 360.83ms         0 [  0.00ns,   0.00ns]   0.00ns   0Search stats                   Bools  Conflicts  Branches  Restarts  BoolPropag  IntegerPropag\n",
      "               'default_lp':  10'659     10'651    11'700        14     145'014        154'610\n",
      "                'fs_random':  11'181     11'120    25'265        13     171'674         56'513\n",
      "                'fs_random':  11'518     11'475    11'784         7      42'667         23'259\n",
      "  'fs_random_quick_restart':   2'668      2'630    78'517       263     512'538         87'834\n",
      "  'fs_random_quick_restart':   2'951      2'670    77'538       267     627'712         85'312\n",
      "                   'max_lp':  10'309     10'301    10'702         7      70'956         71'458\n",
      "                    'no_lp':  10'841     10'833    12'158        16     166'698        176'001\n",
      "                  'probing':   3'256      3'254     9'766       120     317'867         53'292\n",
      "           'probing_max_lp':   3'651      3'583     5'545        77     172'067         44'780\n",
      "            'quick_restart':   2'211      2'190    74'669       219     368'636         80'546\n",
      "      'quick_restart_no_lp':   2'451      2'336    68'709       233     493'643         80'890\n",
      "\n",
      "Lp stats             Component  Iterations  AddedCuts  OPTIMAL  DUAL_F.  DUAL_U.\n",
      "          'max_lp':          1           0          0   10'420        1        0\n",
      "  'probing_max_lp':          1           0          0    4'798       10        0\n",
      "\n",
      ".00ns   0.00ns\n",
      "                'fs_random':         1 [361.35ms, 361.35ms] 361.35ms   0.00ns 361.35ms         1 [  6.39ms,   6.39ms]   6.39ms   0.00ns   6.39ms\n",
      "                'fs_random':         1 [362.54ms, 362.54ms] 362.54ms   0.00ns 362.54ms         1 [ 36.32ms,  36.32ms]  36.32ms   0.00ns  36.32ms\n",
      "  'fs_random_quick_restart':         1 [361.32ms, 361.32ms] 361.32ms   0.00ns 361.32ms         1 [ 86.37ms,  86.37ms]  86.37ms   0.00ns  86.37ms\n",
      "  'fs_random_quick_restart':         1 [361.36ms, 361.36ms] 361.36ms   0.00ns 361.36ms         1 [ 74.13ms,  74.13ms]  74.13ms   0.00ns  74.13ms\n",
      "                   'max_lp':         1 [373.34ms, 373.34ms] 373.34ms   0.00ns 373.34ms         1 [ 23.89ms,  23.89ms]  23.89ms   0.00ns  23.89ms\n",
      "                    'no_lp':         1 [373.25ms, 373.25ms] 373.25ms   0.00ns 373.25ms         1 [ 59.43ms,  59.43ms]  59.43ms   0.00ns  59.43ms\n",
      "                  'probing':         1 [373.33ms, 373.33ms] 373.33ms   0.00ns 373.33ms         1 [ 39.32ms,  39.32ms]  39.32ms   0.00ns  39.32ms\n",
      "           'probing_max_lp':         1 [373.41ms, 373.41ms] 373.41ms   0.00ns 373.41ms         1 [ 24.63ms,  24.63ms]  24.63ms   0.00ns  24.63ms\n",
      "            'quick_restart':         1 [373.09ms, 373.09ms] 373.09ms   0.00ns 373.09ms         1 [ 56.44ms,  56.44ms]  56.44ms   0.00ns  56.44ms\n",
      "      'quick_restart_no_lp':         1 [373.06ms, 373.06ms] 373.06ms   0.00ns 373.06ms         1 [ 71.01ms,  71.01ms]  71.01ms   0.00ns  71.01ms\n",
      "                'rins/rens':         4 [611.59us, 354.58ms]  89.15ms 153.25ms 356.62ms         4 [ 40.00ns,   3.74ms] 935.30us   1.62ms   3.74ms\n",
      "\n",
      "Search stats                   Bools  Conflicts  Branches  Restarts  BoolPropag  IntegerPropag\n",
      "               'default_lp':  10'659     10'651    11'700        14     145'014        154'610\n",
      "                'fs_random':  11'181     11'120    25'265        13     171'674         56'513\n",
      "                'fs_random':  11'518     11'475    11'784         7      42'667         23'259\n",
      "  'fs_random_quick_restart':   2'668      2'630    78'517       263     512'538         87'834\n",
      "  'fs_random_quick_restart':   2'951      2'670    77'538       267     627'712         85'312\n",
      "                   'max_lp':  10'309     10'301    10'702         7      70'956         71'458\n",
      "                    'no_lp':  10'841     10'833    12'158        16     166'698        176'001\n",
      "                  'probing':   3'256      3'254     9'766       120     317'867         53'292\n",
      "           'probing_max_lp':   3'651      3'583     5'545        77     172'067         44'780\n",
      "            'quick_restart':   2'211      2'190    74'669       219     368'636         80'546\n",
      "      'quick_restart_no_lp':   2'451      2'336    68'709       233     493'643         80'890\n",
      "\n",
      "Lp stats             Component  Iterations  AddedCuts  OPTIMAL  DUAL_F.  DUAL_U.\n",
      "          'max_lp':          1           0          0   10'420        1        0\n",
      "  'probing_max_lp':          1           0          0    4'798       10        0\n",
      "\n",
      "Lp dLp dimension                                                   Final dimension of first component\n",
      "          'max_lp':  0 rows, 48 columns, 0 entries with magnitude in [0.000000e+00, 0.000000e+00]\n",
      "  'probing_max_lp':  0 rows, 48 columns, 0 entries with magnitude in [0.000000e+00, 0.000000e+00]\n",
      "\n",
      "imension                                                   Final dimension of first component\n",
      "          'max_lp':  0 rows, 48 columns, 0 entries with magnitude in [0.000000e+00, 0.000000e+00]\n",
      "  'probing_max_lp':  0 rows, 48 columns, 0 entries with magnitude in [0.000000e+00, 0.000000e+00]\n",
      "\n",
      "Lp debug             CutPropag  CutEqPropag  Adjust  Overflow  Bad  BadScaling\n",
      "          'max_lp':          0            0       0         0    0           0\n",
      "  'probing_max_lp':          0            0       0         0    0           0\n",
      "\n",
      "Lp debug             CutPropag  CutEqPropag  Adjust  Overflow  Bad  BadScaling\n",
      "          'max_lp':          0            0       0         0    0           0\n",
      "  'probing_max_lp':          0            0       0         0    0           0\n",
      "\n",
      "Lp pool              Constraints  Updates  Simplif  Merged  Shortened  Split  Strenghtened  Cuts/Call\n",
      "          'max_lp':            0        0        0       0          0      0             0        0/0\n",
      "  'probing_max_lp':            0        0        0       0          0      0             0        0/0\n",
      "\n",
      "Lp pool              Constraints  Updates  Simplif  Merged  Shortened  Split  Strenghtened  Cuts/Call\n",
      "          'max_lp':            0        0        0       0          0      0             0        0/0\n",
      "  'probing_max_lp':            0        0        0       0          0      0             0        0/0\n",
      "\n",
      "LNS stats       Improv/Calls  Closed  Difficulty  TimeLimit\n",
      "  'rins/rens':           4/4     75%        0.82       0.10\n",
      "\n",
      "LNS stats       Improv/Calls  Closed  Difficulty  TimeLimit\n",
      "  'rins/rens':           4/4     75%        0.82       0.10\n",
      "\n",
      "LS stats                   Batches  Restarts  LinMoves  GenMoves  CompoundMoves  WeightUpdates\n",
      "       'fj_long_default':        2         1         0       433            113              0\n",
      "   'fj_long_lin_default':        2         1         0       396              0             44\n",
      "      'fj_short_default':        3         1         0       699            129              0\n",
      "  'fj_short_lin_default':        2         1         0       549             95              0\n",
      "\n",
      "LS stats                   Batches  Restarts  LinMoves  GenMoves  CompoundMoves  WeightUpdates\n",
      "       'fj_long_default':        2         1         0       433            113              0\n",
      "   'fj_long_lin_default':        2         1         0       396              0             44\n",
      "      'fj_short_default':        3         1         0       699            129              0\n",
      "  'fj_short_lin_default':        2         1         0       549             95              0\n",
      "\n",
      "Solution repositories    Added  Queried  Ignored  Synchro\n",
      "  'feasible solutions':      2        0        0        2\n",
      "        'lp solutions':     85        4       65       12\n",
      "                'pump':      0        0\n",
      "\n",
      "Solution repositories    Added  Queried  Ignored  Synchro\n",
      "  'feasible solutions':      2        0        0        2\n",
      "        'lp solutions':     85        4       65       12\n",
      "                'pump':      0        0\n",
      "\n",
      "CpSolverResponse summary:\n",
      "status: OPTIMAL\n",
      "objective: NA\n",
      "best_bound: NA\n",
      "integers: 48\n",
      "booleans: 11181\n",
      "conflicts: 11120\n",
      "branches: 25265\n",
      "propagations: 171674\n",
      "integer_propagations: 56513\n",
      "restarts: 13\n",
      "lp_iterations: 0\n",
      "walltime: 0.386211\n",
      "usertime: 0.386211\n",
      "deterministic_time: 0.532875\n",
      "gap_integral: 0\n",
      "solution_fingerprint: 0x9da1e5995fe5ad52\n",
      "\n",
      "CpSolverResponse summary:\n",
      "status: OPTIMAL\n",
      "objective: NA\n",
      "best_bound: NA\n",
      "integers: 48\n",
      "booleans: 11181\n",
      "conflicts: 11120\n",
      "branches: 25265\n",
      "propagations: 171674\n",
      "integer_propagations: 56513\n",
      "restarts: 13\n",
      "lp_iterations: 0\n",
      "walltime: 0.386211\n",
      "usertime: 0.386211\n",
      "deterministic_time: 0.532875\n",
      "gap_integral: 0\n",
      "solution_fingerprint: 0x9da1e5995fe5ad52\n",
      "\n"
     ]
    }
   ],
   "source": [
    "pack(container, boxes, 10_000)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "mo",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.3"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
